<?xml version="1.0" encoding="utf-8"?>
<!DOCTYPE html>
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:epub="http://www.idpf.org/2007/ops" xml:lang="en" lang="en">
<!-- Created by GNU Texinfo 5.1, http://www.gnu.org/software/texinfo/ -->
<head>
<title>Structure and Interpretation of Computer Programs, 2e: 3.5</title>

<meta name="description" content="Structure and Interpretation of Computer Programs, 2e: 3.5" />
<meta name="keywords" content="Structure and Interpretation of Computer Programs, 2e: 3.5" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<meta name="Generator" content="texi2any" />
<meta charset="utf-8" />
<link href="index.xhtml#Top" rel="start" title="Top" />
<link href="Term-Index.xhtml#Term-Index" rel="index" title="Term Index" />
<link href="index.xhtml#SEC_Contents" rel="contents" title="Table of Contents" />
<link href="Chapter-3.xhtml#Chapter-3" rel="prev" title="Chapter 3" />
<link href="Chapter-4.xhtml#Chapter-4" rel="next" title="Chapter 4" />
<link href="3_002e4.xhtml#g_t3_002e4_002e2" rel="prev" title="3.4.2" />

<link href="css/style.css" rel="stylesheet" type="text/css" />
<link href="css/prettify.css" rel="stylesheet" type="text/css" />

<script src="js/jquery.min.js" type="text/javascript"></script>
<script src="js/footnotes.js" type="text/javascript"></script>
<script src="js/browsertest.js" type="text/javascript"></script>
</head>

<body>
<section><span class="top jump" title="Jump to top"><a href="#pagetop" accesskey="t">⇡</a></span><a id="pagetop"></a><a id="g_t3_002e5"></a>
<nav class="header">
<p>
Next: <a href="Chapter-4.xhtml#Chapter-4" accesskey="n" rel="next">Chapter 4</a>, Prev: <a href="3_002e4.xhtml#g_t3_002e4" accesskey="p" rel="prev">3.4</a>, Up: <a href="Chapter-3.xhtml#Chapter-3" accesskey="u" rel="prev">Chapter 3</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>
<a id="Streams"></a>
<h3 class="section"><span class="secnum">3.5</span><span class="sectitle">Streams</span></h3>

<p>We’ve gained a good understanding of assignment as a tool in modeling, as well
as an appreciation of the complex problems that assignment raises. It is time
to ask whether we could have gone about things in a different way, so as to
avoid some of these problems.  In this section, we explore an alternative
approach to modeling state, based on data structures called <a id="index-streams-1"></a>
<em>streams</em>.
As we shall see, streams can mitigate some of the complexity of modeling state.
</p>
<p>Let’s step back and review where this complexity comes from.  In an attempt to
model real-world phenomena, we made some apparently reasonable decisions: We
modeled real-world objects with local state by computational objects with local
variables.  We identified time variation in the real world with time variation
in the computer.  We implemented the time variation of the states of the model
objects in the computer with assignments to the local variables of the model
objects.
</p>
<p>Is there another approach?  Can we avoid identifying time in the computer with
time in the modeled world?  Must we make the model change with time in order to
model phenomena in a changing world?  Think about the issue in terms of
mathematical functions.  We can describe the time-varying behavior of a
quantity <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> as a function of time <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">(</mo>
    <mi>t</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  If we concentrate on <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math>
instant by instant, we think of it as a changing quantity.  Yet if we
concentrate on the entire time history of values, we do not emphasize
change—the function itself does not change.<a class="footnote_link" id="DOCF180" href="#FOOT180"><sup>180</sup></a>
</p>
<p>If time is measured in discrete steps, then we can model a time function as a
(possibly infinite) sequence.  In this section, we will see how to model change
in terms of sequences that represent the time histories of the systems being
modeled.  To accomplish this, we introduce new data structures called
<a id="index-streams-2"></a>
<em>streams</em>.  From an abstract point of view, a stream is simply a
sequence.  However, we will find that the straightforward implementation of
streams as lists (as in <a href="2_002e2.xhtml#g_t2_002e2_002e1">2.2.1</a>) doesn’t fully reveal the power of
stream processing.  As an alternative, we introduce the technique of
<a id="index-delayed-evaluation-1"></a>
<em>delayed evaluation</em>, which enables us to represent very large (even
infinite) sequences as streams.
</p>
<p>Stream processing lets us model systems that have state without ever using
assignment or mutable data.  This has important implications, both theoretical
and practical, because we can build models that avoid the drawbacks inherent in
introducing assignment.  On the other hand, the stream framework raises
difficulties of its own, and the question of which modeling technique leads to
more modular and more easily maintained systems remains open.
</p>

<a id="g_t3_002e5_002e1"></a>
<a id="Streams-Are-Delayed-Lists"></a>
<h4 class="subsection"><span class="secnum">3.5.1</span><span class="sectitle">Streams Are Delayed Lists</span></h4>

<p>As we saw in <a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>, sequences can serve as standard interfaces
for combining program modules.  We formulated powerful abstractions for
manipulating sequences, such as <code>map</code>, <code>filter</code>, and
<code>accumulate</code>, that capture a wide variety of operations in a manner that
is both succinct and elegant.
</p>
<p>Unfortunately, if we represent sequences as lists, this elegance is bought at
the price of severe inefficiency with respect to both the time and space
required by our computations.  When we represent manipulations on sequences as
transformations of lists, our programs must construct and copy data structures
(which may be huge) at every step of a process.
</p>
<p>To see why this is true, let us compare two programs for computing the sum of
all the prime numbers in an interval.  The first program is written in standard
iterative style:<a class="footnote_link" id="DOCF181" href="#FOOT181"><sup>181</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-primes a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter count accum</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> count b</span><span class="clo">)</span><span class="pln"> accum</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">prime? count</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> count </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> count accum</span><span class="clo">)))</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> count </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> accum</span><span class="clo">))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter a </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>The second program performs the same computation using the sequence operations
of <a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sum-primes a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">accumulate 
   </span><span class="pun">+</span><span class="pln">
   </span><span class="lit">0</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">filter prime? </span><span class="opn">(</span><span class="pln">enumerate-interval a b</span><span class="clo">))))</span></pre></div>

<p>In carrying out the computation, the first program needs to store only the sum
being accumulated.  In contrast, the filter in the second program cannot do any
testing until <code>enumerate-interval</code> has constructed a complete list of the
numbers in the interval.  The filter generates another list, which in turn is
passed to <code>accumulate</code> before being collapsed to form a sum.  Such large
intermediate storage is not needed by the first program, which we can think of
as enumerating the interval incrementally, adding each prime to the sum as it
is generated.
</p>
<p>The inefficiency in using lists becomes painfully apparent if we use the
sequence paradigm to compute the second prime in the interval from 10,000 to
1,000,000 by evaluating the expression
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">car</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pln">filter 
       prime?
       </span><span class="opn">(</span><span class="pln">enumerate-interval </span><span class="lit">10000</span><span class="pln"> </span><span class="lit">1000000</span><span class="clo">))))</span></pre></div>

<p>This expression does find the second prime, but the computational overhead is
outrageous.  We construct a list of almost a million integers, filter this list
by testing each element for primality, and then ignore almost all of the
result.  In a more traditional programming style, we would interleave the
enumeration and the filtering, and stop when we reached the second prime.
</p>
<p>Streams are a clever idea that allows one to use sequence manipulations without
incurring the costs of manipulating sequences as lists.  With streams we can
achieve the best of both worlds: We can formulate programs elegantly as
sequence manipulations, while attaining the efficiency of incremental
computation.  The basic idea is to arrange to construct a stream only
partially, and to pass the partial construction to the program that consumes
the stream.  If the consumer attempts to access a part of the stream that has
not yet been constructed, the stream will automatically construct just enough
more of itself to produce the required part, thus preserving the illusion that
the entire stream exists.  In other words, although we will write programs as
if we were processing complete sequences, we design our stream implementation
to automatically and transparently interleave the construction of the stream
with its use.
</p>
<p>On the surface, streams are just lists with different names for the procedures
that manipulate them.  There is a constructor, <code>cons-stream</code>, and two
selectors, <code>stream-car</code> and <code>stream-cdr</code>, which satisfy the
constraints
</p>
<div class="example">
<pre class="example">(stream-car (cons-stream x y)) = x
(stream-cdr (cons-stream x y)) = y
</pre></div>

<p>There is a distinguishable object, <code>the-empty-stream</code>, which cannot be the
result of any <code>cons-stream</code> operation, and which can be identified with
the predicate <code>stream-null?</code>.<a class="footnote_link" id="DOCF182" href="#FOOT182"><sup>182</sup></a>  Thus we can
make and use streams, in just the same way as we can make and use lists, to
represent aggregate data arranged in a sequence.  In particular, we can build
stream analogs of the list operations from <a href="Chapter-2.xhtml#Chapter-2">Chapter 2</a>, such as
<code>list-ref</code>, <code>map</code>, and <code>for-each</code>:<a class="footnote_link" id="DOCF183" href="#FOOT183"><sup>183</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-ref s n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> n </span><span class="lit">0</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">stream-ref </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-map proc s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? s</span><span class="clo">)</span><span class="pln">
      the-empty-stream
      </span><span class="opn">(</span><span class="pln">cons-stream 
       </span><span class="opn">(</span><span class="pln">proc </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">stream-map proc </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-for-each proc s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? s</span><span class="clo">)</span><span class="pln">
      </span><span class="lit">'done</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">proc </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">))</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">stream-for-each proc 
                         </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)))))</span></pre></div>

<p><code>Stream-for-each</code> is useful for viewing streams:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display-stream s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-for-each display-line s</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">display-line x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">newline</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">display x</span><span class="clo">))</span></pre></div>

<p>To make the stream implementation automatically and transparently interleave
the construction of a stream with its use, we will arrange for the <code>cdr</code>
of a stream to be evaluated when it is accessed by the <code>stream-cdr</code>
procedure rather than when the stream is constructed by <code>cons-stream</code>.
This implementation choice is reminiscent of our discussion of rational numbers
in <a href="2_002e1.xhtml#g_t2_002e1_002e2">2.1.2</a>, where we saw that we can choose to implement rational
numbers so that the reduction of numerator and denominator to lowest terms is
performed either at construction time or at selection time.  The two
rational-number implementations produce the same data abstraction, but the
choice has an effect on efficiency.  There is a similar relationship between
streams and ordinary lists.  As a data abstraction, streams are the same as
lists.  The difference is the time at which the elements are evaluated.  With
ordinary lists, both the <code>car</code> and the <code>cdr</code> are evaluated at
construction time.  With streams, the <code>cdr</code> is evaluated at selection
time.
</p>
<p>Our implementation of streams will be based on a special form called
<code>delay</code>.  Evaluating <code>(delay ⟨<var>exp</var>⟩)</code> does not evaluate the
expression <code>⟨</code><var>exp</var><code>⟩</code>, but rather returns a so-called 
<a id="index-delayed-object"></a>
<em>delayed object</em>, which we can think of as a “promise” to evaluate 
<code>⟨</code><var>exp</var><code>⟩</code> at some
future time.  As a companion to <code>delay</code>, there is a procedure called
<code>force</code> that takes a delayed object as argument and performs the
evaluation—in effect, forcing the <code>delay</code> to fulfill its promise.  We
will see below how <code>delay</code> and <code>force</code> can be implemented, but first
let us use these to construct streams.
</p>
<p><code>Cons-stream</code> is a special form defined so that
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">cons-stream ⟨</span><var><span class="pln">a</span></var><span class="pln">⟩ ⟨</span><var><span class="pln">b</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is equivalent to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> ⟨</span><var><span class="pln">a</span></var><span class="pln">⟩ </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> ⟨</span><var><span class="pln">b</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>What this means is that we will construct streams using pairs.  However, rather
than placing the value of the rest of the stream into the <code>cdr</code> of the
pair we will put there a promise to compute the rest if it is ever requested.
<code>Stream-car</code> and <code>stream-cdr</code> can now be defined as procedures:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> stream</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-cdr stream</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">force </span><span class="opn">(</span><span class="kwd">cdr</span><span class="pln"> stream</span><span class="clo">)))</span></pre></div>

<p><code>Stream-car</code> selects the <code>car</code> of the pair; <code>stream-cdr</code> selects
the <code>cdr</code> of the pair and evaluates the delayed expression found there to
obtain the rest of the stream.<a class="footnote_link" id="DOCF184" href="#FOOT184"><sup>184</sup></a>
</p>
<a id="The-stream-implementation-in-action"></a>
<h5 class="subsubheading">The stream implementation in action</h5>

<p>To see how this implementation behaves, let us analyze the “outrageous” prime
computation we saw above, reformulated in terms of streams:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">stream-car 
 </span><span class="opn">(</span><span class="pln">stream-cdr
  </span><span class="opn">(</span><span class="pln">stream-filter 
   prime? </span><span class="opn">(</span><span class="pln">stream-enumerate-interval 
           </span><span class="lit">10000</span><span class="pln"> </span><span class="lit">1000000</span><span class="clo">))))</span></pre></div>

<p>We will see that it does indeed work efficiently.
</p>
<p>We begin by calling <code>stream-enumerate-interval</code> with the arguments 10,000
and 1,000,000.  <code>Stream-enumerate-interval</code> is the stream analog of
<code>enumerate-interval</code> (<a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-enumerate-interval low high</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pun">&gt;</span><span class="pln"> low high</span><span class="clo">)</span><span class="pln">
      the-empty-stream
      </span><span class="opn">(</span><span class="pln">cons-stream
       low
       </span><span class="opn">(</span><span class="pln">stream-enumerate-interval </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> low </span><span class="lit">1</span><span class="clo">)</span><span class="pln">
                                  high</span><span class="clo">))))</span></pre></div>

<p>and thus the result returned by <code>stream-enumerate-interval</code>, formed by the
<code>cons-stream</code>, is<a class="footnote_link" id="DOCF185" href="#FOOT185"><sup>185</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">10000</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">stream-enumerate-interval 
         </span><span class="lit">10001</span><span class="pln"> 
         </span><span class="lit">1000000</span><span class="clo">)))</span></pre></div>

<p>That is, <code>stream-enumerate-interval</code> returns a stream represented as a
pair whose <code>car</code> is 10,000 and whose <code>cdr</code> is a promise to enumerate
more of the interval if so requested.  This stream is now filtered for primes,
using the stream analog of the <code>filter</code> procedure (<a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-filter pred stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">stream-null? stream</span><span class="clo">)</span><span class="pln"> 
         the-empty-stream</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">pred </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">))</span><span class="pln">
         </span><span class="opn">(</span><span class="pln">cons-stream 
          </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">stream-filter 
           pred
           </span><span class="opn">(</span><span class="pln">stream-cdr stream</span><span class="clo">))))</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-filter 
               pred 
               </span><span class="opn">(</span><span class="pln">stream-cdr stream</span><span class="clo">)))))</span></pre></div>

<p><code>Stream-filter</code> tests the <code>stream-car</code> of the stream (the <code>car</code>
of the pair, which is 10,000).  Since this is not prime, <code>stream-filter</code>
examines the <code>stream-cdr</code> of its input stream.  The call to
<code>stream-cdr</code> forces evaluation of the delayed
<code>stream-enumerate-interval</code>, which now returns
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">10001</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> 
        </span><span class="opn">(</span><span class="pln">stream-enumerate-interval 
         </span><span class="lit">10002</span><span class="pln"> 
         </span><span class="lit">1000000</span><span class="clo">)))</span></pre></div>

<p><code>Stream-filter</code> now looks at the <code>stream-car</code> of this stream, 10,001,
sees that this is not prime either, forces another <code>stream-cdr</code>, and so
on, until <code>stream-enumerate-interval</code> yields the prime 10,007, whereupon
<code>stream-filter</code>, according to its definition, returns
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">cons-stream 
 </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">)</span><span class="pln">
 </span><span class="opn">(</span><span class="pln">stream-filter pred </span><span class="opn">(</span><span class="pln">stream-cdr stream</span><span class="clo">)))</span></pre></div>

<p>which in this case is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">10007</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">stream-filter
         prime?
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">10008</span><span class="pln">
               </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">stream-enumerate-interval 
                  </span><span class="lit">10009</span><span class="pln"> </span><span class="lit">1000000</span><span class="clo">))))))</span></pre></div>

<p>This result is now passed to <code>stream-cdr</code> in our original expression.
This forces the delayed <code>stream-filter</code>, which in turn keeps forcing the
delayed <code>stream-enumerate-interval</code> until it finds the next prime, which
is 10,009.  Finally, the result passed to <code>stream-car</code> in our original
expression is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">10009</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">stream-filter
         prime?
         </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> </span><span class="lit">10010</span><span class="pln">
               </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">stream-enumerate-interval 
                  </span><span class="lit">10011</span><span class="pln"> </span><span class="lit">1000000</span><span class="clo">))))))</span></pre></div>

<p><code>Stream-car</code> returns 10,009, and the computation is complete.  Only as
many integers were tested for primality as were necessary to find the second
prime, and the interval was enumerated only as far as was necessary to feed the
prime filter.
</p>
<p>In general, we can think of delayed evaluation as “demand-driven”
programming, whereby each stage in the stream process is activated only enough
to satisfy the next stage.  What we have done is to decouple the actual order
of events in the computation from the apparent structure of our procedures.  We
write procedures as if the streams existed “all at once” when, in reality,
the computation is performed incrementally, as in traditional programming
styles.
</p>
<a id="Implementing-delay-and-force"></a>
<h5 class="subsubheading">Implementing <code>delay</code> and <code>force</code></h5>

<p>Although <code>delay</code> and <code>force</code> may seem like mysterious operations,
their implementation is really quite straightforward.  <code>Delay</code> must
package an expression so that it can be evaluated later on demand, and we can
accomplish this simply by treating the expression as the body of a procedure.
<code>Delay</code> can be a special form such that
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> ⟨</span><var><span class="pln">exp</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p>is syntactic sugar for
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">exp</span></var><span class="pln">⟩</span><span class="clo">)</span></pre></div>

<p><code>Force</code> simply calls the procedure (of no arguments) produced by
<code>delay</code>, so we can implement <code>force</code> as a procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">force delayed-object</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">delayed-object</span><span class="clo">))</span></pre></div>

<p>This implementation suffices for <code>delay</code> and <code>force</code> to work as
advertised, but there is an important optimization that we can include.  In
many applications, we end up forcing the same delayed object many times.  This
can lead to serious inefficiency in recursive programs involving streams.  (See
<a href="#Exercise-3_002e57">Exercise 3.57</a>.)  The solution is to build delayed objects so that the
first time they are forced, they store the value that is computed.  Subsequent
forcings will simply return the stored value without repeating the computation.
In other words, we implement <code>delay</code> as a special-purpose memoized
procedure similar to the one described in <a href="3_002e3.xhtml#Exercise-3_002e27">Exercise 3.27</a>.  One way to
accomplish this is to use the following procedure, which takes as argument a
procedure (of no arguments) and returns a memoized version of the procedure.
The first time the memoized procedure is run, it saves the computed result.  On
subsequent evaluations, it simply returns the result.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">memo-proc proc</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">already-run? false</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">result false</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">not already-run?</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">begin</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> result </span><span class="opn">(</span><span class="pln">proc</span><span class="clo">))</span><span class="pln">
                 </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> already-run? true</span><span class="clo">)</span><span class="pln">
                 result</span><span class="clo">)</span><span class="pln">
          result</span><span class="clo">))))</span></pre></div>

<p><code>Delay</code> is then defined so that <code>(delay ⟨<var>exp</var>⟩)</code> is equivalent
to
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">memo-proc </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln"> ⟨</span><var><span class="pln">exp</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>and <code>force</code> is as defined previously.<a class="footnote_link" id="DOCF186" href="#FOOT186"><sup>186</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e50"></a>Exercise 3.50:</strong> Complete the following
definition, which generalizes <code>stream-map</code> to allow procedures that take
multiple arguments, analogous to <code>map</code> in <a href="2_002e2.xhtml#g_t2_002e2_002e1">2.2.1</a>, 
<a href="2_002e2.xhtml#Footnote-78">Footnote 78</a>.
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-map proc </span><span class="pun">.</span><span class="pln"> argstreams</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">⟨</span><span class="pun">??</span><span class="pln">⟩ </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> argstreams</span><span class="clo">))</span><span class="pln">
      the-empty-stream
      </span><span class="opn">(</span><span class="pln">⟨</span><span class="pun">??</span><span class="pln">⟩
       </span><span class="opn">(</span><span class="pln">apply proc </span><span class="opn">(</span><span class="pln">map ⟨</span><span class="pun">??</span><span class="pln">⟩ argstreams</span><span class="clo">))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">apply stream-map
              </span><span class="opn">(</span><span class="kwd">cons</span><span class="pln"> proc 
                    </span><span class="opn">(</span><span class="pln">map ⟨</span><span class="pun">??</span><span class="pln">⟩ 
                         argstreams</span><span class="clo">))))))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e51"></a>Exercise 3.51:</strong> In order to take a closer look at
delayed evaluation, we will use the following procedure, which simply returns
its argument after printing it:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">show x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">display-line x</span><span class="clo">)</span><span class="pln">
  x</span><span class="clo">)</span></pre></div>

<p>What does the interpreter print in response to evaluating each expression in
the following sequence?<a class="footnote_link" id="DOCF187" href="#FOOT187"><sup>187</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> x 
  </span><span class="opn">(</span><span class="pln">stream-map 
   show 
   </span><span class="opn">(</span><span class="pln">stream-enumerate-interval </span><span class="lit">0</span><span class="pln"> </span><span class="lit">10</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">stream-ref x </span><span class="lit">5</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">stream-ref x </span><span class="lit">7</span><span class="clo">)</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e52"></a>Exercise 3.52:</strong> Consider the sequence of
expressions
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> sum </span><span class="lit">0</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accum x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> sum </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> x sum</span><span class="clo">))</span><span class="pln">
  sum</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> seq 
  </span><span class="opn">(</span><span class="pln">stream-map 
   accum 
   </span><span class="opn">(</span><span class="pln">stream-enumerate-interval </span><span class="lit">1</span><span class="pln"> </span><span class="lit">20</span><span class="clo">)))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> y </span><span class="opn">(</span><span class="pln">stream-filter even? seq</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> z 
  </span><span class="opn">(</span><span class="pln">stream-filter 
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> 
     </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">remainder x </span><span class="lit">5</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span><span class="pln"> seq</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">stream-ref y </span><span class="lit">7</span><span class="clo">)</span><span class="pln">
</span><span class="opn">(</span><span class="pln">display-stream z</span><span class="clo">)</span></pre></div>

<p>What is the value of <code>sum</code> after each of the above expressions is
evaluated?  What is the printed response to evaluating the <code>stream-ref</code>
and <code>display-stream</code> expressions?  Would these responses differ if we had
implemented <code>(delay ⟨<var>exp</var>⟩)</code> simply as <code>(lambda () ⟨<var>exp</var>⟩)</code>
without using the optimization provided by <code>memo-proc</code>?  Explain.
</p></blockquote>

<a id="g_t3_002e5_002e2"></a>
<a id="Infinite-Streams"></a>
<h4 class="subsection"><span class="secnum">3.5.2</span><span class="sectitle">Infinite Streams</span></h4>

<p>We have seen how to support the illusion of manipulating streams as complete
entities even though, in actuality, we compute only as much of the stream as we
need to access.  We can exploit this technique to represent sequences
efficiently as streams, even if the sequences are very long.  What is more
striking, we can use streams to represent sequences that are infinitely long.
For instance, consider the following definition of the stream of positive
integers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">integers-starting-from n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream 
   n </span><span class="opn">(</span><span class="pln">integers-starting-from </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> n </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> integers </span><span class="opn">(</span><span class="pln">integers-starting-from </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p>This makes sense because <code>integers</code> will be a pair whose <code>car</code> is 1
and whose <code>cdr</code> is a promise to produce the integers beginning with 2.
This is an infinitely long stream, but in any given time we can examine only a
finite portion of it.  Thus, our programs will never know that the entire
infinite stream is not there.
</p>
<p>Using <code>integers</code> we can define other infinite streams, such as the stream
of integers that are not divisible by 7:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">divisible? x y</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">remainder x y</span><span class="clo">)</span><span class="pln"> </span><span class="lit">0</span><span class="clo">))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> no-sevens
  </span><span class="opn">(</span><span class="pln">stream-filter </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> 
                   </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">divisible? x </span><span class="lit">7</span><span class="clo">)))</span><span class="pln">
                 integers</span><span class="clo">))</span></pre></div>

<p>Then we can find integers not divisible by 7 simply by accessing elements of
this stream:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">stream-ref no-sevens </span><span class="lit">100</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">117</span></i>
</pre></div>

<p>In analogy with <code>integers</code>, we can define the infinite stream of Fibonacci
numbers:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">fibgen a b</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream a </span><span class="opn">(</span><span class="pln">fibgen b </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> a b</span><span class="clo">))))</span><span class="pln">
</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> fibs </span><span class="opn">(</span><span class="pln">fibgen </span><span class="lit">0</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span></pre></div>

<p><code>Fibs</code> is a pair whose <code>car</code> is 0 and whose <code>cdr</code> is a promise
to evaluate <code>(fibgen 1 1)</code>.  When we evaluate this delayed <code>(fibgen 1
1)</code>, it will produce a pair whose <code>car</code> is 1 and whose <code>cdr</code> is a
promise to evaluate <code>(fibgen 1 2)</code>, and so on.
</p>
<p>For a look at a more exciting infinite stream, we can generalize the
<code>no-sevens</code> example to construct the infinite stream of prime numbers,
using a method known as the <a id="index-sieve-of-Eratosthenes"></a>
<em>sieve of Eratosthenes</em>.<a class="footnote_link" id="DOCF188" href="#FOOT188"><sup>188</sup></a>
We start with the integers beginning with 2, which is the first prime.  To get
the rest of the primes, we start by filtering the multiples of 2 from the rest
of the integers.  This leaves a stream beginning with 3, which is the next
prime.  Now we filter the multiples of 3 from the rest of this stream.  This
leaves a stream beginning with 5, which is the next prime, and so on.  In other
words, we construct the primes by a sieving process, described as follows: To
sieve a stream <code>S</code>, form a stream whose first element is the first element
of <code>S</code> and the rest of which is obtained by filtering all multiples of the
first element of <code>S</code> out of the rest of <code>S</code> and sieving the
result. This process is readily described in terms of stream operations:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sieve stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream
   </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">sieve </span><span class="opn">(</span><span class="pln">stream-filter
           </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln">
             </span><span class="opn">(</span><span class="pln">not </span><span class="opn">(</span><span class="pln">divisible? 
                   x </span><span class="opn">(</span><span class="pln">stream-car stream</span><span class="clo">))))</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">stream-cdr stream</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> primes 
  </span><span class="opn">(</span><span class="pln">sieve </span><span class="opn">(</span><span class="pln">integers-starting-from </span><span class="lit">2</span><span class="clo">)))</span></pre></div>

<p>Now to find a particular prime we need only ask for it:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">stream-ref primes </span><span class="lit">50</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">233</span></i>
</pre></div>

<p>It is interesting to contemplate the signal-processing system set up by
<code>sieve</code>, shown in the “Henderson diagram” in 
<a href="#Figure-3_002e31">Figure 3.31</a>.<a class="footnote_link" id="DOCF189" href="#FOOT189"><sup>189</sup></a>  The input stream
feeds into an “un<code>cons</code>er” that separates the first element of the
stream from the rest of the stream.  The first element is used to construct a
divisibility filter, through which the rest is passed, and the output of the
filter is fed to another sieve box.  Then the original first element is
<code>cons</code>ed onto the output of the internal sieve to form the output stream.
Thus, not only is the stream infinite, but the signal processor is also
infinite, because the sieve contains a sieve within it.
</p>
<figure class="float">
<a id="Figure-3_002e31"></a>
<object style="width: 54.05ex; height: 27.89ex;" data="fig/chap3/Fig3.31a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.31:</strong> The prime sieve viewed as a signal-processing system.</p>
</figcaption>
</figure>

<a id="Defining-streams-implicitly"></a>
<h5 class="subsubheading">Defining streams implicitly</h5>

<p>The <code>integers</code> and <code>fibs</code> streams above were defined by specifying
“generating” procedures that explicitly compute the stream elements one by
one. An alternative way to specify streams is to take advantage of delayed
evaluation to define streams implicitly.  For example, the following expression
defines the stream <code>ones</code> to be an infinite stream of ones:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> ones </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">1</span><span class="pln"> ones</span><span class="clo">))</span></pre></div>

<p>This works much like the definition of a recursive procedure: <code>ones</code> is a
pair whose <code>car</code> is 1 and whose <code>cdr</code> is a promise to evaluate
<code>ones</code>.  Evaluating the <code>cdr</code> gives us again a 1 and a promise to
evaluate <code>ones</code>, and so on.
</p>
<p>We can do more interesting things by manipulating streams with operations such
as <code>add-streams</code>, which produces the elementwise sum of two given
streams:<a class="footnote_link" id="DOCF190" href="#FOOT190"><sup>190</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-streams s1 s2</span><span class="clo">)</span><span class="pln"> 
  </span><span class="opn">(</span><span class="pln">stream-map </span><span class="pun">+</span><span class="pln"> s1 s2</span><span class="clo">))</span></pre></div>

<p>Now we can define the integers as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> integers 
  </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-streams ones integers</span><span class="clo">)))</span></pre></div>

<p>This defines <code>integers</code> to be a stream whose first element is 1 and the
rest of which is the sum of <code>ones</code> and <code>integers</code>.  Thus, the second
element of <code>integers</code> is 1 plus the first element of <code>integers</code>, or
2; the third element of <code>integers</code> is 1 plus the second element of
<code>integers</code>, or 3; and so on.  This definition works because, at any point,
enough of the <code>integers</code> stream has been generated so that we can feed it
back into the definition to produce the next integer.
</p>
<p>We can define the Fibonacci numbers in the same style:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> fibs 
  </span><span class="opn">(</span><span class="pln">cons-stream 
   </span><span class="lit">0</span><span class="pln"> </span><span class="opn">(</span><span class="pln">cons-stream
      </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-streams 
         </span><span class="opn">(</span><span class="pln">stream-cdr fibs</span><span class="clo">)</span><span class="pln"> fibs</span><span class="clo">))))</span></pre></div>

<p>This definition says that <code>fibs</code> is a stream beginning with 0 and 1, such
that the rest of the stream can be generated by adding <code>fibs</code> to itself
shifted by one place:
</p>
<div class="example">
<pre class="example">    1 1 2 3 5  8 13 21 <span class="roman">…</span> = <code>(stream-cdr fibs)</code>
    0 1 1 2 3  5  8 13 <span class="roman">…</span> = <code>fibs</code>
0 1 1 2 3 5 8 13 21 34 <span class="roman">…</span> = <code>fibs</code>
</pre></div>

<p><code>Scale-stream</code> is another useful procedure in formulating such stream
definitions.  This multiplies each item in a stream by a given constant:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scale-stream stream factor</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-map
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> x factor</span><span class="clo">))</span><span class="pln">
   stream</span><span class="clo">))</span></pre></div>

<p>For example,
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> double 
  </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">scale-stream double </span><span class="lit">2</span><span class="clo">)))</span></pre></div>

<p>produces the stream of powers of 2: 1, 2, 4, 8, 16, 32, ….
</p>
<p>An alternate definition of the stream of primes can be given by starting with
the integers and filtering them by testing for primality.  We will need the
first prime, 2, to get started:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> primes
  </span><span class="opn">(</span><span class="pln">cons-stream
   </span><span class="lit">2</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-filter 
      prime? </span><span class="opn">(</span><span class="pln">integers-starting-from </span><span class="lit">3</span><span class="clo">))))</span></pre></div>

<p>This definition is not so straightforward as it appears, because we will test
whether a number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime by checking whether <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is divisible by a
prime (not by just any integer) less than or equal to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msqrt>
    <mi>n</mi>
  </msqrt>
</math>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">prime? n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter ps</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square </span><span class="opn">(</span><span class="pln">stream-car ps</span><span class="clo">))</span><span class="pln"> n</span><span class="clo">)</span><span class="pln"> true</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">((</span><span class="pln">divisible? n </span><span class="opn">(</span><span class="pln">stream-car ps</span><span class="clo">))</span><span class="pln"> false</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="kwd">else</span><span class="pln"> </span><span class="opn">(</span><span class="pln">iter </span><span class="opn">(</span><span class="pln">stream-cdr ps</span><span class="clo">)))))</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">iter primes</span><span class="clo">))</span></pre></div>

<p>This is a recursive definition, since <code>primes</code> is defined in terms of the
<code>prime?</code> predicate, which itself uses the <code>primes</code> stream.  The
reason this procedure works is that, at any point, enough of the <code>primes</code>
stream has been generated to test the primality of the numbers we need to check
next.  That is, for every <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> we test for primality, either <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is not
prime (in which case there is a prime already generated that divides it) or
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math> is prime (in which case there is a prime already generated—i.e., a
prime less than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>—that is greater than
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msqrt>
    <mi>n</mi>
  </msqrt>
</math>).<a class="footnote_link" id="DOCF191" href="#FOOT191"><sup>191</sup></a>
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e53"></a>Exercise 3.53:</strong> Without running the program,
describe the elements of the stream defined by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> s </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">add-streams s s</span><span class="clo">)))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e54"></a>Exercise 3.54:</strong> Define a procedure
<code>mul-streams</code>, analogous to <code>add-streams</code>, that produces the
elementwise product of its two input streams.  Use this together with the
stream of <code>integers</code> to complete the following definition of the stream
whose <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> element (counting from 0) is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>n</mi>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math> factorial:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> factorials 
  </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-streams ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e55"></a>Exercise 3.55:</strong> Define a procedure
<code>partial-sums</code> that takes as argument a stream <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> and returns the
stream whose elements are <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mn>0</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>S</mi>
      <mn>0</mn>
    </msub>
    <mo>+</mo>
    <msub>
      <mi>S</mi>
      <mn>1</mn>
    </msub>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>S</mi>
      <mn>0</mn>
    </msub>
    <mo>+</mo>
    <msub>
      <mi>S</mi>
      <mn>1</mn>
    </msub>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>S</mi>
      <mn>2</mn>
    </msub>
    <mo>,</mo>
    <mo>…<!-- … --></mo>
  </mrow>
</math>.  
For example, <code>(partial-sums integers)</code> should be the
stream 1, 3, 6, 10, 15, ….
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e56"></a>Exercise 3.56:</strong> A famous problem, first raised by
R. Hamming, is to enumerate, in ascending order with no repetitions, all
positive integers with no prime factors other than 2, 3, or 5.  One obvious way
to do this is to simply test each integer in turn to see whether it has any
factors other than 2, 3, and 5.  But this is very inefficient, since, as the
integers get larger, fewer and fewer of them fit the requirement.  As an
alternative, let us call the required stream of numbers <code>S</code> and notice the
following facts about it.
</p>
<ul>
<li> <code>S</code> begins with 1.

</li><li> The elements of <code>(scale-stream S 2)</code> are also
elements of <code>S</code>.

</li><li> The same is true for <code>(scale-stream S 3)</code>
and <code>(scale-stream S 5)</code>.

</li><li> These are all the elements of <code>S</code>.

</li></ul>

<p>Now all we have to do is combine elements from these sources.  For this we
define a procedure <code>merge</code> that combines two ordered streams into one
ordered result stream, eliminating repetitions:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">merge s1 s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pln">stream-null? s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">((</span><span class="pln">stream-null? s2</span><span class="clo">)</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
         </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">s1car </span><span class="opn">(</span><span class="pln">stream-car s1</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">s2car </span><span class="opn">(</span><span class="pln">stream-car s2</span><span class="clo">)))</span><span class="pln">
           </span><span class="opn">(</span><span class="kwd">cond</span><span class="pln"> </span><span class="opn">((</span><span class="pun">&lt;</span><span class="pln"> s1car s2car</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">cons-stream 
                   s1car 
                   </span><span class="opn">(</span><span class="pln">merge </span><span class="opn">(</span><span class="pln">stream-cdr s1</span><span class="clo">)</span><span class="pln"> 
                          s2</span><span class="clo">)))</span><span class="pln">
                 </span><span class="opn">((</span><span class="pun">&gt;</span><span class="pln"> s1car s2car</span><span class="clo">)</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">cons-stream 
                   s2car 
                   </span><span class="opn">(</span><span class="pln">merge s1 
                          </span><span class="opn">(</span><span class="pln">stream-cdr s2</span><span class="clo">))))</span><span class="pln">
                 </span><span class="opn">(</span><span class="kwd">else</span><span class="pln">
                  </span><span class="opn">(</span><span class="pln">cons-stream 
                   s1car
                   </span><span class="opn">(</span><span class="pln">merge 
                    </span><span class="opn">(</span><span class="pln">stream-cdr s1</span><span class="clo">)</span><span class="pln">
                    </span><span class="opn">(</span><span class="pln">stream-cdr s2</span><span class="clo">)))))))))</span></pre></div>

<p>Then the required stream may be constructed with <code>merge</code>, as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> S </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">merge ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))</span></pre></div>

<p>Fill in the missing expressions in the places marked <code>⟨??⟩</code> above.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e57"></a>Exercise 3.57:</strong> How many additions are performed
when we compute the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> Fibonacci number using the definition of
<code>fibs</code> based on the <code>add-streams</code> procedure?  Show that the number of
additions would be exponentially greater if we had implemented <code>(delay ⟨<var>exp</var>⟩)</code> 
simply as <code>(lambda () ⟨<var>exp</var>⟩)</code>, without using the
optimization provided by the <code>memo-proc</code> procedure described in 
<a href="#g_t3_002e5_002e1">3.5.1</a>.<a class="footnote_link" id="DOCF192" href="#FOOT192"><sup>192</sup></a>
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e58"></a>Exercise 3.58:</strong> Give an interpretation of the
stream computed by the following procedure:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">expand num den radix</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream
   </span><span class="opn">(</span><span class="pln">quotient </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> num radix</span><span class="clo">)</span><span class="pln"> den</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">expand </span><span class="opn">(</span><span class="pln">remainder </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> num radix</span><span class="clo">)</span><span class="pln"> den</span><span class="clo">)</span><span class="pln"> 
           den 
           radix</span><span class="clo">)))</span></pre></div>

<p>(<code>Quotient</code> is a primitive that returns the integer quotient of two
integers.)  What are the successive elements produced by <code>(expand 1 7
10)</code>?  What is produced by <code>(expand 3 8 10)</code>?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e59"></a>Exercise 3.59:</strong> In <a href="2_002e5.xhtml#g_t2_002e5_002e3">2.5.3</a> we saw how
to implement a polynomial arithmetic system representing polynomials as lists
of terms.  In a similar way, we can work with <a id="index-power-series"></a>
<em>power series</em>, such as
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <msup>
          <mi>e</mi>
          <mi>x</mi>
        </msup>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mn>1</mn>
        <mo>+</mo>
        <mi>x</mi>
        <mo>+</mo>
        <mfrac>
          <mn>1</mn>
          <mn>2</mn>
        </mfrac>
        <msup>
          <mi>x</mi>
          <mn>2</mn>
        </msup>
        <mo>+</mo>
        <mfrac>
          <mn>1</mn>
          <mrow>
            <mn>3</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>2</mn>
          </mrow>
        </mfrac>
        <msup>
          <mi>x</mi>
          <mn>3</mn>
        </msup>
        <mo>+</mo>
        <mfrac>
          <mn>1</mn>
          <mrow>
            <mn>4</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>3</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>2</mn>
          </mrow>
        </mfrac>
        <msup>
          <mi>x</mi>
          <mn>4</mn>
        </msup>
        <mo>+</mo>
        <mo>…<!-- … --></mo>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>cos</mi>
        <mo>⁡<!-- ⁡ --></mo>
        <mi>x</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mn>1</mn>
        <mo>−<!-- − --></mo>
        <mfrac>
          <mn>1</mn>
          <mn>2</mn>
        </mfrac>
        <msup>
          <mi>x</mi>
          <mn>2</mn>
        </msup>
        <mo>+</mo>
        <mfrac>
          <mn>1</mn>
          <mrow>
            <mn>4</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>3</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>2</mn>
          </mrow>
        </mfrac>
        <msup>
          <mi>x</mi>
          <mn>4</mn>
        </msup>
        <mo>−<!-- − --></mo>
        <mo>…<!-- … --></mo>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>sin</mi>
        <mo>⁡<!-- ⁡ --></mo>
        <mi>x</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mi>x</mi>
        <mo>−<!-- − --></mo>
        <mfrac>
          <mn>1</mn>
          <mrow>
            <mn>3</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>2</mn>
          </mrow>
        </mfrac>
        <msup>
          <mi>x</mi>
          <mn>3</mn>
        </msup>
        <mo>+</mo>
        <mfrac>
          <mn>1</mn>
          <mrow>
            <mn>5</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>4</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>3</mn>
            <mo>⋅<!-- ⋅ --></mo>
            <mn>2</mn>
          </mrow>
        </mfrac>
        <msup>
          <mi>x</mi>
          <mn>5</mn>
        </msup>
        <mo>−<!-- − --></mo>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
  </mtable>
</math>
represented as infinite streams.  We will represent the series <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>0</mn>
    </msub>
    <mo>+</mo>
    <msub>
      <mi>a</mi>
      <mn>1</mn>
    </msub>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>2</mn>
    </msub>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>3</mn>
    </msub>
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
    <mo>+</mo>
    <mo>…<!-- … --></mo>
  </mrow>
</math> as the stream whose
elements are the coefficients <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>0</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>1</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>2</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>3</mn>
  </msub>
</math>, ….
</p>
<ol>
<li> The integral of the series <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>0</mn>
    </msub>
    <mo>+</mo>
    <msub>
      <mi>a</mi>
      <mn>1</mn>
    </msub>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>2</mn>
    </msub>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>3</mn>
    </msub>
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
    <mo>+</mo>
    <mo>…<!-- … --></mo>
  </mrow>
</math> is the series
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>c</mi>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>a</mi>
      <mn>0</mn>
    </msub>
    <mi>x</mi>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>2</mn>
    </mfrac>
    <msub>
      <mi>a</mi>
      <mn>1</mn>
    </msub>
    <msup>
      <mi>x</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>3</mn>
    </mfrac>
    <msub>
      <mi>a</mi>
      <mn>2</mn>
    </msub>
    <msup>
      <mi>x</mi>
      <mn>3</mn>
    </msup>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>4</mn>
    </mfrac>
    <msub>
      <mi>a</mi>
      <mn>3</mn>
    </msub>
    <msup>
      <mi>x</mi>
      <mn>4</mn>
    </msup>
    <mo>+</mo>
    <mo>…<!-- … --></mo>
    <mo>,</mo>
  </mrow>
</math>
where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>c</mi>
</math> is any constant.  Define a procedure <code>integrate-series</code> that
takes as input a stream <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>0</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>1</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>2</mn>
  </msub>
</math>, … representing a power
series and returns the stream <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>a</mi>
    <mn>0</mn>
  </msub>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>2</mn>
      </mfrac>
    </mrow>
    <msub>
      <mi>a</mi>
      <mn>1</mn>
    </msub>
  </mrow>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mn>1</mn>
        <mn>3</mn>
      </mfrac>
    </mrow>
    <msub>
      <mi>a</mi>
      <mn>2</mn>
    </msub>
  </mrow>
</math>, … of
coefficients of the non-constant terms of the integral of the series.  (Since
the result has no constant term, it doesn’t represent a power series; when we
use <code>integrate-series</code>, we will <code>cons</code> on the appropriate constant.)

</li><li> The function <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo stretchy="false">↦<!-- ↦ --></mo>
    <msup>
      <mi>e</mi>
      <mi>x</mi>
    </msup>
  </mrow>
</math> is its own derivative.  This implies that
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>e</mi>
    <mi>x</mi>
  </msup>
</math> and the integral of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>e</mi>
    <mi>x</mi>
  </msup>
</math> are the same series, except for the
constant term, which is <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>e</mi>
      <mn>0</mn>
    </msup>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math>.  Accordingly, we can generate the series
for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>e</mi>
    <mi>x</mi>
  </msup>
</math> as

<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> exp-series
  </span><span class="opn">(</span><span class="pln">cons-stream 
   </span><span class="lit">1</span><span class="pln"> </span><span class="opn">(</span><span class="pln">integrate-series exp-series</span><span class="clo">)))</span></pre></div>

<p>Show how to generate the series for sine and cosine, starting from the facts
that the derivative of sine is cosine and the derivative of cosine is the
negative of sine:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> cosine-series 
  </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">1</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> sine-series
  </span><span class="opn">(</span><span class="pln">cons-stream </span><span class="lit">0</span><span class="pln"> ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">))</span></pre></div>
</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e60"></a>Exercise 3.60:</strong> With power series represented as
streams of coefficients as in <a href="#Exercise-3_002e59">Exercise 3.59</a>, adding series is implemented
by <code>add-streams</code>.  Complete the definition of the following procedure for
multiplying series:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">mul-series s1 s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream ⟨</span><span class="pun">??</span><span class="pln">⟩ </span><span class="opn">(</span><span class="pln">add-streams ⟨</span><span class="pun">??</span><span class="pln">⟩ ⟨</span><span class="pun">??</span><span class="pln">⟩</span><span class="clo">)))</span></pre></div>

<p>You can test your procedure by verifying that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>sin</mi>
      <mn>2</mn>
    </msup>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>x</mi>
    <mo>+</mo>
    <msup>
      <mi>cos</mi>
      <mn>2</mn>
    </msup>
    <mo>⁡<!-- ⁡ --></mo>
    <mi>x</mi>
    <mo>=</mo>
    <mn>1</mn>
    <mo>,</mo>
  </mrow>
</math>
using the series from <a href="#Exercise-3_002e59">Exercise 3.59</a>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e61"></a>Exercise 3.61:</strong> Let <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> be a power series
(<a href="#Exercise-3_002e59">Exercise 3.59</a>) whose constant term is 1.  Suppose we want to find the
power series <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>S</mi>
  </mrow>
</math>, that is, the series <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>X</mi>
</math> such that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mi>X</mi>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math>.
Write <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo>=</mo>
    <mn>1</mn>
    <mo>+</mo>
    <msub>
      <mi>S</mi>
      <mi>R</mi>
    </msub>
  </mrow>
</math> where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mi>R</mi>
  </msub>
</math> is the part of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> after the
constant term.  Then we can solve for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>X</mi>
</math> as follows:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <mi>S</mi>
        <mo>⋅<!-- ⋅ --></mo>
        <mi>X</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mn>1</mn>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <mn>1</mn>
        <mo>+</mo>
        <msub>
          <mi>S</mi>
          <mi>R</mi>
        </msub>
        <mo stretchy="false">)</mo>
        <mo>⋅<!-- ⋅ --></mo>
        <mi>X</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mn>1</mn>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>X</mi>
        <mo>+</mo>
        <msub>
          <mi>S</mi>
          <mi>R</mi>
        </msub>
        <mo>⋅<!-- ⋅ --></mo>
        <mi>X</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mn>1</mn>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mi>X</mi>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mn>1</mn>
        <mo>−<!-- − --></mo>
        <msub>
          <mi>S</mi>
          <mi>R</mi>
        </msub>
        <mo>⋅<!-- ⋅ --></mo>
        <mi>X</mi>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>
In other words, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>X</mi>
</math> is the power series whose constant term is 1 and whose
higher-order terms are given by the negative of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mi>R</mi>
  </msub>
</math> times <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>X</mi>
</math>.  Use
this idea to write a procedure <code>invert-unit-series</code> that computes <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>1</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>S</mi>
  </mrow>
</math>
for a power series <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> with constant term 1.  You will need to use
<code>mul-series</code> from <a href="#Exercise-3_002e60">Exercise 3.60</a>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e62"></a>Exercise 3.62:</strong> Use the results of <a href="#Exercise-3_002e60">Exercise 3.60</a> 
and <a href="#Exercise-3_002e61">Exercise 3.61</a> to define a procedure <code>div-series</code> that
divides two power series.  <code>Div-series</code> should work for any two series,
provided that the denominator series begins with a nonzero constant term.  (If
the denominator has a zero constant term, then <code>div-series</code> should signal
an error.)  Show how to use <code>div-series</code> together with the result of
<a href="#Exercise-3_002e59">Exercise 3.59</a> to generate the power series for tangent.
</p></blockquote>

<a id="g_t3_002e5_002e3"></a>
<a id="Exploiting-the-Stream-Paradigm"></a>
<h4 class="subsection"><span class="secnum">3.5.3</span><span class="sectitle">Exploiting the Stream Paradigm</span></h4>

<p>Streams with delayed evaluation can be a powerful modeling tool, providing many
of the benefits of local state and assignment.  Moreover, they avoid some of
the theoretical tangles that accompany the introduction of assignment into a
programming language.
</p>
<p>The stream approach can be illuminating because it allows us to build systems
with different module boundaries than systems organized around assignment to
state variables.  For example, we can think of an entire time series (or
signal) as a focus of interest, rather than the values of the state variables
at individual moments.  This makes it convenient to combine and compare
components of state from different moments.
</p>
<a id="Formulating-iterations-as-stream-processes"></a>
<h5 class="subsubheading">Formulating iterations as stream processes</h5>

<p>In section <a href="1_002e2.xhtml#g_t1_002e2_002e1">1.2.1</a>, we introduced iterative processes, which proceed by
updating state variables.  We know now that we can represent state as a
“timeless” stream of values rather than as a set of variables to be updated.
Let’s adopt this perspective in revisiting the square-root procedure from
<a href="1_002e1.xhtml#g_t1_002e1_002e7">1.1.7</a>.  Recall that the idea is to generate a sequence of better
and better guesses for the square root of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>x</mi>
</math> by applying over and over again
the procedure that improves guesses:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt-improve guess x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">average guess </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> x guess</span><span class="clo">)))</span></pre></div>

<p>In our original <code>sqrt</code> procedure, we made these guesses be the successive
values of a state variable. Instead we can generate the infinite stream of
guesses, starting with an initial guess of 1:<a class="footnote_link" id="DOCF193" href="#FOOT193"><sup>193</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt-stream x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> guesses
    </span><span class="opn">(</span><span class="pln">cons-stream 
     </span><span class="lit">1.0</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-map
          </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">guess</span><span class="clo">)</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">sqrt-improve guess x</span><span class="clo">))</span><span class="pln">
          guesses</span><span class="clo">)))</span><span class="pln">
  guesses</span><span class="clo">)</span><span class="pln">

</span><span class="opn">(</span><span class="pln">display-stream </span><span class="opn">(</span><span class="pln">sqrt-stream </span><span class="lit">2</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">1.</span></i><span class="pln">
</span><i><span class="lit">1.5</span></i><span class="pln">
</span><i><span class="lit">1.4166666666666665</span></i><span class="pln">
</span><i><span class="lit">1.4142156862745097</span></i><span class="pln">
</span><i><span class="lit">1.4142135623746899</span></i><span class="pln">
</span><span class="roman"><span class="pun">…</span></span>
</pre></div>

<p>We can generate more and more terms of the stream to get better and better
guesses.  If we like, we can write a procedure that keeps generating terms
until the answer is good enough.  (See <a href="#Exercise-3_002e64">Exercise 3.64</a>.)
</p>
<p>Another iteration that we can treat in the same way is to generate an
approximation to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>, based upon the alternating series that we saw in
<a href="1_002e3.xhtml#g_t1_002e3_002e1">1.3.1</a>:
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mi>π<!-- π --></mi>
      <mn>4</mn>
    </mfrac>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mn>1</mn>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>3</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>5</mn>
    </mfrac>
  </mrow>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>7</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mo>…<!-- … --></mo>
    <mo>.</mo>
  </mrow>
</math>
We first generate the stream of summands of the series (the reciprocals of the
odd integers, with alternating signs).  Then we take the stream of sums of more
and more terms (using the <code>partial-sums</code> procedure of <a href="#Exercise-3_002e55">Exercise 3.55</a>)
and scale the result by 4:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-summands n</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream 
   </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">1.0</span><span class="pln"> n</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">stream-map </span><span class="pun">-</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pi-summands </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> n </span><span class="lit">2</span><span class="clo">)))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> pi-stream
  </span><span class="opn">(</span><span class="pln">scale-stream 
   </span><span class="opn">(</span><span class="pln">partial-sums </span><span class="opn">(</span><span class="pln">pi-summands </span><span class="lit">1</span><span class="clo">))</span><span class="pln"> </span><span class="lit">4</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="pln">display-stream pi-stream</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">4.</span></i><span class="pln">
</span><i><span class="lit">2.666666666666667</span></i><span class="pln">
</span><i><span class="lit">3.466666666666667</span></i><span class="pln">
</span><i><span class="lit">2.8952380952380956</span></i><span class="pln">
</span><i><span class="lit">3.3396825396825403</span></i><span class="pln">
</span><i><span class="lit">2.9760461760461765</span></i><span class="pln">
</span><i><span class="lit">3.2837384837384844</span></i><span class="pln">
</span><i><span class="lit">3.017071817071818</span></i><span class="pln">
</span><span class="roman"><span class="pun">…</span></span>
</pre></div>

<p>This gives us a stream of better and better approximations to <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>,
although the approximations converge rather slowly.  Eight terms of the
sequence bound the value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> between 3.284 and 3.017.
</p>
<p>So far, our use of the stream of states approach is not much different from
updating state variables.  But streams give us an opportunity to do some
interesting tricks.  For example, we can transform a stream with a
<a id="index-sequence-accelerator"></a>
<em>sequence accelerator</em> that converts a sequence of approximations to a
new sequence that converges to the same value as the original, only faster.
</p>
<p>One such accelerator, due to the eighteenth-century Swiss mathematician
Leonhard Euler, works well with sequences that are partial sums of alternating
series (series of terms with alternating signs).  In Euler’s technique, if
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>S</mi>
    <mi>n</mi>
  </msub>
</math> is the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>n</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> term of the original sum sequence, then the
accelerated sequence has terms
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <msub>
    <mi>S</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>n</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mrow class="MJX-TeXAtom-ORD">
      <mfrac>
        <mrow>
          <mo stretchy="false">(</mo>
          <msub>
            <mi>S</mi>
            <mrow class="MJX-TeXAtom-ORD">
              <mi>n</mi>
              <mo>+</mo>
              <mn>1</mn>
            </mrow>
          </msub>
          <mo>−<!-- − --></mo>
          <msub>
            <mi>S</mi>
            <mi>n</mi>
          </msub>
          <msup>
            <mo stretchy="false">)</mo>
            <mn>2</mn>
          </msup>
        </mrow>
        <mrow>
          <msub>
            <mi>S</mi>
            <mrow class="MJX-TeXAtom-ORD">
              <mi>n</mi>
              <mo>−<!-- − --></mo>
              <mn>1</mn>
            </mrow>
          </msub>
          <mo>−<!-- − --></mo>
          <mn>2</mn>
          <msub>
            <mi>S</mi>
            <mi>n</mi>
          </msub>
          <mo>+</mo>
          <msub>
            <mi>S</mi>
            <mrow class="MJX-TeXAtom-ORD">
              <mi>n</mi>
              <mo>+</mo>
              <mn>1</mn>
            </mrow>
          </msub>
        </mrow>
      </mfrac>
    </mrow>
    <mo>.</mo>
  </mrow>
</math>
Thus, if the original sequence is represented as a stream of values, the
transformed sequence is given by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">euler-transform s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">s0 </span><span class="opn">(</span><span class="pln">stream-ref s </span><span class="lit">0</span><span class="clo">))</span><span class="pln">     </span><span class="com">; </span><var><span class="com">Sₙ</span></var><span class="com">₋₁</span><span class="pln">
        </span><span class="opn">(</span><span class="pln">s1 </span><span class="opn">(</span><span class="pln">stream-ref s </span><span class="lit">1</span><span class="clo">))</span><span class="pln">     </span><span class="com">; </span><var><span class="com">Sₙ</span></var><span class="pln">
        </span><span class="opn">(</span><span class="pln">s2 </span><span class="opn">(</span><span class="pln">stream-ref s </span><span class="lit">2</span><span class="clo">)))</span><span class="pln">    </span><span class="com">; </span><var><span class="com">Sₙ</span></var><span class="com">₊₁</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">cons-stream 
     </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> s2 </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pln">square </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> s2 s1</span><span class="clo">))</span><span class="pln">
              </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> s0 </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> </span><span class="lit">-2</span><span class="pln"> s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">)))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">euler-transform </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)))))</span></pre></div>

<p>We can demonstrate Euler acceleration with our sequence of approximations to
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">display-stream 
 </span><span class="opn">(</span><span class="pln">euler-transform pi-stream</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">3.166666666666667</span></i><span class="pln">
</span><i><span class="lit">3.1333333333333337</span></i><span class="pln">
</span><i><span class="lit">3.1452380952380956</span></i><span class="pln">
</span><i><span class="lit">3.13968253968254</span></i><span class="pln">
</span><i><span class="lit">3.1427128427128435</span></i><span class="pln">
</span><i><span class="lit">3.1408813408813416</span></i><span class="pln">
</span><i><span class="lit">3.142071817071818</span></i><span class="pln">
</span><i><span class="lit">3.1412548236077655</span></i><span class="pln">
</span><span class="roman"><span class="pun">…</span></span>
</pre></div>

<p>Even better, we can accelerate the accelerated sequence, and recursively
accelerate that, and so on.  Namely, we create a stream of streams (a structure
we’ll call a <a id="index-tableau"></a>
<em>tableau</em>) in which each stream is the transform of the
preceding one:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-tableau transform s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream 
   s
   </span><span class="opn">(</span><span class="pln">make-tableau
    transform
    </span><span class="opn">(</span><span class="pln">transform s</span><span class="clo">))))</span></pre></div>

<p>The tableau has the form
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="center center center center center center" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>00</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>01</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>02</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>03</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>04</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>10</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>11</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>12</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>13</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd/>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>20</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>21</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <msub>
          <mi>s</mi>
          <mrow class="MJX-TeXAtom-ORD">
            <mn>22</mn>
          </mrow>
        </msub>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd/>
      <mtd/>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
      <mtd/>
      <mtd/>
    </mtr>
  </mtable>
</math>
Finally, we form a sequence by taking the first term in each row of the
tableau:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">accelerated-sequence transform s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-map stream-car
              </span><span class="opn">(</span><span class="pln">make-tableau transform s</span><span class="clo">)))</span></pre></div>

<p>We can demonstrate this kind of “super-acceleration” of the <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>
sequence:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">display-stream 
 </span><span class="opn">(</span><span class="pln">accelerated-sequence euler-transform
                       pi-stream</span><span class="clo">))</span><span class="pln">
</span><i><span class="lit">4.</span></i><span class="pln">
</span><i><span class="lit">3.166666666666667</span></i><span class="pln">
</span><i><span class="lit">3.142105263157895</span></i><span class="pln">
</span><i><span class="lit">3.141599357319005</span></i><span class="pln">
</span><i><span class="lit">3.1415927140337785</span></i><span class="pln">
</span><i><span class="lit">3.1415926539752927</span></i><span class="pln">
</span><i><span class="lit">3.1415926535911765</span></i><span class="pln">
</span><i><span class="lit">3.141592653589778</span></i><span class="pln">
</span><span class="roman"><span class="pun">…</span></span>
</pre></div>

<p>The result is impressive.  Taking eight terms of the sequence yields the
correct value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> to 14 decimal places.  If we had used only the
original <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> sequence, we would need to compute on the order of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mn>10</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mn>13</mn>
    </mrow>
  </msup>
</math>
terms (i.e., expanding the series far enough so that the individual terms are
less than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mn>10</mn>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>−<!-- − --></mo>
      <mn>13</mn>
    </mrow>
  </msup>
</math>) to get that much accuracy!
</p>
<p>We could have implemented these acceleration techniques without using streams.
But the stream formulation is particularly elegant and convenient because the
entire sequence of states is available to us as a data structure that can be
manipulated with a uniform set of operations.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e63"></a>Exercise 3.63:</strong> Louis Reasoner asks why the
<code>sqrt-stream</code> procedure was not written in the following more
straightforward way, without the local variable <code>guesses</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt-stream x</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream 
   </span><span class="lit">1.0</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">stream-map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">guess</span><span class="clo">)</span><span class="pln">
                 </span><span class="opn">(</span><span class="pln">sqrt-improve guess x</span><span class="clo">))</span><span class="pln">
               </span><span class="opn">(</span><span class="pln">sqrt-stream x</span><span class="clo">))))</span></pre></div>

<p>Alyssa P. Hacker replies that this version of the procedure is considerably
less efficient because it performs redundant computation.  Explain Alyssa’s
answer.  Would the two versions still differ in efficiency if our
implementation of <code>delay</code> used only <code>(lambda () ⟨<var>exp</var>⟩)</code> without
using the optimization provided by <code>memo-proc</code> (<a href="#g_t3_002e5_002e1">3.5.1</a>)?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e64"></a>Exercise 3.64:</strong> Write a procedure
<code>stream-limit</code> that takes as arguments a stream and a number (the
tolerance).  It should examine the stream until it finds two successive
elements that differ in absolute value by less than the tolerance, and return
the second of the two elements.  Using this, we could compute square roots up
to a given tolerance by
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt x tolerance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">stream-limit </span><span class="opn">(</span><span class="pln">sqrt-stream x</span><span class="clo">)</span><span class="pln"> tolerance</span><span class="clo">))</span></pre></div>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e65"></a>Exercise 3.65:</strong> Use the series
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mi>ln</mi>
  <mo>⁡<!-- ⁡ --></mo>
  <mn>2</mn>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mn>1</mn>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>2</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>3</mn>
    </mfrac>
  </mrow>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mfrac>
      <mn>1</mn>
      <mn>4</mn>
    </mfrac>
  </mrow>
  <mo>+</mo>
  <mo>…<!-- … --></mo>
</math>
to compute three sequences of approximations to the natural logarithm of 2, in
the same way we did above for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>.  How rapidly do these sequences
converge?
</p></blockquote>

<a id="Infinite-streams-of-pairs"></a>
<h5 class="subsubheading">Infinite streams of pairs</h5>

<p>In <a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>, we saw how the sequence paradigm handles traditional
nested loops as processes defined on sequences of pairs.  If we generalize this
technique to infinite streams, then we can write programs that are not easily
represented as loops, because the “looping” must range over an infinite set.
</p>
<p>For example, suppose we want to generalize the <code>prime-sum-pairs</code> procedure
of <a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a> to produce the stream of pairs of <em>all</em> integers
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
</math> such that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>+</mo>
    <mi>j</mi>
  </mrow>
</math> is prime.  If
<code>int-pairs</code> is the sequence of all pairs of integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> with
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
</math>, then our required stream is simply<a class="footnote_link" id="DOCF194" href="#FOOT194"><sup>194</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">stream-filter 
 </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pair</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">prime? </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">car</span><span class="pln"> pair</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="kwd">cadr</span><span class="pln"> pair</span><span class="clo">))))</span><span class="pln">
 int-pairs</span><span class="clo">)</span></pre></div>

<p>Our problem, then, is to produce the stream <code>int-pairs</code>.  More generally,
suppose we have two streams <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo>=</mo>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>S</mi>
      <mi>i</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>T</mi>
    <mo>=</mo>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>T</mi>
      <mi>j</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math>,
and imagine the infinite rectangular array
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="center center center center" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>0</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>0</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>0</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
      <mtd/>
      <mtd/>
      <mtd/>
    </mtr>
  </mtable>
</math>
We wish to generate a stream that contains all the pairs in the array that lie
on or above the diagonal, i.e., the pairs
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="center center center center" rowspacing="4pt" columnspacing="1em">
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>0</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd/>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd/>
      <mtd/>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
  </mtable>
</math>
(If we take both <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math> to be the stream of integers, then this will
be our desired stream <code>int-pairs</code>.)
</p>
<p>Call the general stream of pairs <code>(pairs S T)</code>, and consider it to be
composed of three parts: the pair <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>S</mi>
      <mn>0</mn>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>T</mi>
      <mn>0</mn>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, the rest of the pairs in
the first row, and the remaining pairs:<a class="footnote_link" id="DOCF195" href="#FOOT195"><sup>195</sup></a>
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="center center center center" rowspacing="4pt" columnspacing="1em" rowlines="solid none" columnlines="solid none none">
    <mtr>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>0</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>0</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>1</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>1</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd/>
      <mtd>
        <mo stretchy="false">(</mo>
        <msub>
          <mi>S</mi>
          <mn>2</mn>
        </msub>
        <mo>,</mo>
        <msub>
          <mi>T</mi>
          <mn>2</mn>
        </msub>
        <mo stretchy="false">)</mo>
      </mtd>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd/>
      <mtd/>
      <mtd/>
      <mtd>
        <mo>…<!-- … --></mo>
      </mtd>
    </mtr>
  </mtable>
</math>
Observe that the third piece in this decomposition (pairs that are not in the
first row) is (recursively) the pairs formed from <code>(stream-cdr S)</code> and
<code>(stream-cdr T)</code>.  Also note that the second piece (the rest of the first
row) is
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">stream-map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> 
              </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
            </span><span class="opn">(</span><span class="pln">stream-cdr t</span><span class="clo">))</span></pre></div>

<p>Thus we can form our stream of pairs as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pairs s t</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream
   </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-car t</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">⟨</span><var><span class="pln">combine-in-some-way</span></var><span class="pln">⟩
    </span><span class="opn">(</span><span class="pln">stream-map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> 
                  </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">stream-cdr t</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">pairs </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)</span><span class="pln">
           </span><span class="opn">(</span><span class="pln">stream-cdr t</span><span class="clo">)))))</span></pre></div>

<p>In order to complete the procedure, we must choose some way to combine the two
inner streams.  One idea is to use the stream analog of the <code>append</code>
procedure from <a href="2_002e2.xhtml#g_t2_002e2_002e1">2.2.1</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-append s1 s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? s1</span><span class="clo">)</span><span class="pln">
      s2
      </span><span class="opn">(</span><span class="pln">cons-stream 
       </span><span class="opn">(</span><span class="pln">stream-car s1</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">stream-append </span><span class="opn">(</span><span class="pln">stream-cdr s1</span><span class="clo">)</span><span class="pln"> s2</span><span class="clo">))))</span></pre></div>

<p>This is unsuitable for infinite streams, however, because it takes all the
elements from the first stream before incorporating the second stream.  In
particular, if we try to generate all pairs of positive integers using
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">pairs integers integers</span><span class="clo">)</span></pre></div>

<p>our stream of results will first try to run through all pairs with the first
integer equal to 1, and hence will never produce pairs with any other value of
the first integer.
</p>
<p>To handle infinite streams, we need to devise an order of combination that
ensures that every element will eventually be reached if we let our program run
long enough.  An elegant way to accomplish this is with the following
<code>interleave</code> procedure:<a class="footnote_link" id="DOCF196" href="#FOOT196"><sup>196</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">interleave s1 s2</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? s1</span><span class="clo">)</span><span class="pln">
      s2
      </span><span class="opn">(</span><span class="pln">cons-stream 
       </span><span class="opn">(</span><span class="pln">stream-car s1</span><span class="clo">)</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">interleave s2 </span><span class="opn">(</span><span class="pln">stream-cdr s1</span><span class="clo">)))))</span></pre></div>

<p>Since <code>interleave</code> takes elements alternately from the two streams, every
element of the second stream will eventually find its way into the interleaved
stream, even if the first stream is infinite.
</p>
<p>We can thus generate the required stream of pairs as
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pairs s t</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream
   </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-car t</span><span class="clo">))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">interleave
    </span><span class="opn">(</span><span class="pln">stream-map </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> 
                  </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
                </span><span class="opn">(</span><span class="pln">stream-cdr t</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">pairs </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-cdr t</span><span class="clo">)))))</span></pre></div>

<blockquote>
<p><strong><a id="Exercise-3_002e66"></a>Exercise 3.66:</strong> Examine the stream <code>(pairs
integers integers)</code>. Can you make any general comments about the order in which
the pairs are placed into the stream? For example, approximately how many pairs precede
the pair (1, 100)?  the pair (99, 100)? the pair (100, 100)? (If you can make
precise mathematical statements here, all the better. But feel free to give
more qualitative answers if you find yourself getting bogged down.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e67"></a>Exercise 3.67:</strong> Modify the <code>pairs</code> procedure
so that <code>(pairs integers integers)</code> will produce the stream of <em>all</em>
pairs of integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> (without the condition <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
</math>).  Hint:
You will need to mix in an additional stream.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e68"></a>Exercise 3.68:</strong> Louis Reasoner thinks that
building a stream of pairs from three parts is unnecessarily complicated.
Instead of separating the pair <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>S</mi>
      <mn>0</mn>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>T</mi>
      <mn>0</mn>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math> from the rest of the pairs in
the first row, he proposes to work with the whole first row, as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">pairs s t</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">interleave
   </span><span class="opn">(</span><span class="pln">stream-map
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">x</span><span class="clo">)</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pln">list </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln"> x</span><span class="clo">))</span><span class="pln">
    t</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">pairs </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)</span><span class="pln">
          </span><span class="opn">(</span><span class="pln">stream-cdr t</span><span class="clo">))))</span></pre></div>

<p>Does this work?  Consider what happens if we evaluate <code>(pairs integers
integers)</code> using Louis’s definition of <code>pairs</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e69"></a>Exercise 3.69:</strong> Write a procedure <code>triples</code>
that takes three infinite streams, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>S</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>T</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>U</mi>
</math>, and produces the
stream of triples <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>S</mi>
      <mi>i</mi>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>T</mi>
      <mi>j</mi>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>U</mi>
      <mi>k</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math> such that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>k</mi>
  </mrow>
</math>.  
Use <code>triples</code> to generate the stream of all Pythagorean
triples of positive integers, i.e., the triples <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo>,</mo>
    <mi>k</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> such that
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>i</mi>
      <mn>2</mn>
    </msup>
    <mo>+</mo>
    <msup>
      <mi>j</mi>
      <mn>2</mn>
    </msup>
    <mo>=</mo>
    <msup>
      <mi>k</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e70"></a>Exercise 3.70:</strong> It would be nice to be able to
generate streams in which the pairs appear in some useful order, rather than in
the order that results from an <em>ad hoc</em> interleaving process.  We can use
a technique similar to the <code>merge</code> procedure of <a href="#Exercise-3_002e56">Exercise 3.56</a>, if we
define a way to say that one pair of integers is “less than” another.  One
way to do this is to define a “weighting function” <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>W</mi>
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and
stipulate that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>i</mi>
      <mn>1</mn>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>j</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math> is less than <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <msub>
      <mi>i</mi>
      <mn>2</mn>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>j</mi>
      <mn>2</mn>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math> if
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>W</mi>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>i</mi>
      <mn>1</mn>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>j</mi>
      <mn>1</mn>
    </msub>
    <mo stretchy="false">)</mo>
    <mo>&lt;</mo>
  </mrow>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>W</mi>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>i</mi>
      <mn>2</mn>
    </msub>
    <mo>,</mo>
    <msub>
      <mi>j</mi>
      <mn>2</mn>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  Write a procedure
<code>merge-weighted</code> that is like <code>merge</code>, except that
<code>merge-weighted</code> takes an additional argument <code>weight</code>, which is a
procedure that computes the weight of a pair, and is used to determine the
order in which elements should appear in the resulting merged
stream.<a class="footnote_link" id="DOCF197" href="#FOOT197"><sup>197</sup></a>  Using this, generalize <code>pairs</code> to a procedure
<code>weighted-pairs</code> that takes two streams, together with a procedure that
computes a weighting function, and generates the stream of pairs, ordered
according to weight.  Use your procedure to generate
</p>
<ol>
<li> the stream of all pairs of positive integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
</math>
ordered according to the sum <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>+</mo>
    <mi>j</mi>
  </mrow>
</math>,

</li><li> the stream of all pairs of positive integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>i</mi>
    <mo>≤<!-- ≤ --></mo>
    <mi>j</mi>
  </mrow>
</math>,
where neither <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> nor <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>j</mi>
</math> is divisible by 2, 3, or 5, and the pairs are
ordered according to the sum <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mn>2</mn>
    <mi>i</mi>
    <mo>+</mo>
    <mn>3</mn>
    <mi>j</mi>
    <mo>+</mo>
    <mn>5</mn>
    <mi>i</mi>
    <mi>j</mi>
  </mrow>
</math>.

</li></ol>
</blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e71"></a>Exercise 3.71:</strong> Numbers that can be expressed as
the sum of two cubes in more than one way are sometimes called
<a id="index-Ramanujan-numbers"></a>
<em>Ramanujan numbers</em>, in honor of the mathematician Srinivasa
Ramanujan.<a class="footnote_link" id="DOCF198" href="#FOOT198"><sup>198</sup></a> Ordered streams of pairs provide an elegant
solution to the problem of computing these numbers.  To find a number that can
be written as the sum of two cubes in two different ways, we need only generate
the stream of pairs of integers <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> weighted according to the sum
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>i</mi>
      <mn>3</mn>
    </msup>
    <mo>+</mo>
    <msup>
      <mi>j</mi>
      <mn>3</mn>
    </msup>
  </mrow>
</math> (see <a href="#Exercise-3_002e70">Exercise 3.70</a>), then search the stream for two
consecutive pairs with the same weight.  Write a procedure to generate the
Ramanujan numbers.  The first such number is 1,729.  What are the next five?
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e72"></a>Exercise 3.72:</strong> In a similar way to <a href="#Exercise-3_002e71">Exercise 3.71</a> 
generate a stream of all numbers that can be written as the sum of two
squares in three different ways (showing how they can be so written).
</p></blockquote>

<a id="Streams-as-signals"></a>
<h5 class="subsubheading">Streams as signals</h5>

<p>We began our discussion of streams by describing them as computational analogs
of the “signals” in signal-processing systems.  In fact, we can use streams
to model signal-processing systems in a very direct way, representing the
values of a signal at successive time intervals as consecutive elements of a
stream.  For instance, we can implement an <a id="index-integrator"></a>
<em>integrator</em> or
<a id="index-summer"></a>
<em>summer</em> that, for an input stream <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>x</mi>
    <mo>=</mo>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>x</mi>
      <mi>i</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math>, an initial
value <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math>, and a small increment <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math>, accumulates the sum
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <msub>
    <mi>S</mi>
    <mi>i</mi>
  </msub>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mi>C</mi>
  <mo>+</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <munderover>
      <mo>∑<!-- ∑ --></mo>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>j</mi>
        <mo>=</mo>
        <mn>1</mn>
      </mrow>
      <mi>i</mi>
    </munderover>
    <msub>
      <mi>x</mi>
      <mi>j</mi>
    </msub>
    <mspace width="thinmathspace"/>
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math>
and returns the stream of values <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>S</mi>
    <mo>=</mo>
    <mo stretchy="false">(</mo>
    <msub>
      <mi>S</mi>
      <mi>i</mi>
    </msub>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.  The following
<code>integral</code> procedure is reminiscent of the “implicit style” definition
of the stream of integers (<a href="#g_t3_002e5_002e2">3.5.2</a>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">integral integrand initial-value dt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> int
    </span><span class="opn">(</span><span class="pln">cons-stream 
     initial-value
     </span><span class="opn">(</span><span class="pln">add-streams </span><span class="opn">(</span><span class="pln">scale-stream integrand dt</span><span class="clo">)</span><span class="pln">
                  int</span><span class="clo">)))</span><span class="pln">
  int</span><span class="clo">)</span></pre></div>

<p><a href="#Figure-3_002e32">Figure 3.32</a> is a picture of a signal-processing system that corresponds
to the <code>integral</code> procedure.  The input stream is scaled by <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math> and
passed through an adder, whose output is passed back through the same adder.
The self-reference in the definition of <code>int</code> is reflected in the figure
by the feedback loop that connects the output of the adder to one of the
inputs.
</p>
<figure class="float">
<a id="Figure-3_002e32"></a>
<object style="width: 59.32ex; height: 20.20ex;" data="fig/chap3/Fig3.32a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.32:</strong> The <code>integral</code> procedure viewed as a signal-processing system.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-3_002e73"></a>Exercise 3.73:</strong> We can model electrical circuits
using streams to represent the values of currents or voltages at a sequence of
times.  For instance, suppose we have an <a id="index-RC-circuit"></a>
<em>RC circuit</em> consisting of a
resistor of resistance <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>R</mi>
</math> and a capacitor of capacitance <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math> in series.
The voltage response <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>v</mi>
</math> of the circuit to an injected current <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> is
determined by the formula in <a href="#Figure-3_002e33">Figure 3.33</a>, whose structure is shown by the
accompanying signal-flow diagram.
</p>
<figure class="float">
<a id="Figure-3_002e33"></a>
<object style="width: 50.08ex; height: 37.47ex;" data="fig/chap3/Fig3.33a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.33:</strong> An RC circuit and the associated signal-flow diagram.</p>
</figcaption>
</figure>

<p>Write a procedure <code>RC</code> that models this circuit.  <code>RC</code> should take as
inputs the values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>R</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math> and should return a procedure
that takes as inputs a stream representing the current <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> and an initial
value for the capacitor voltage <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>v</mi>
    <mn>0</mn>
  </msub>
</math> and produces as output the stream of
voltages <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>v</mi>
</math>.  For example, you should be able to use <code>RC</code> to model an
RC circuit with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>R</mi>
</math> = 5 ohms, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math> = 1 farad, and a 0.5-second time step by
evaluating <code>(define RC1 (RC 5 1 0.5))</code>.  This defines <code>RC1</code> as a
procedure that takes a stream representing the time sequence of currents and an
initial capacitor voltage and produces the output stream of voltages.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e74"></a>Exercise 3.74:</strong> Alyssa P. Hacker is designing a
system to process signals coming from physical sensors.  One important feature
she wishes to produce is a signal that describes the <a id="index-zero-crossings"></a>
<em>zero crossings</em>
of the input signal.  That is, the resulting signal should be <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math> whenever the
input signal changes from negative to positive, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math> whenever the input signal
changes from positive to negative, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mn>0</mn>
</math> otherwise.  (Assume that the sign of a
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mn>0</mn>
</math> input is positive.)  For example, a typical input signal with its associated
zero-crossing signal would be
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">2</span><span class="pln"> </span><span class="lit">1.5</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0.5</span><span class="pln"> </span><span class="lit">-0.1</span><span class="pln"> </span><span class="lit">-2</span><span class="pln"> </span><span class="lit">-3</span><span class="pln"> </span><span class="lit">-2</span><span class="pln"> </span><span class="lit">-0.5</span><span class="pln"> </span><span class="lit">0.2</span><span class="pln"> </span><span class="lit">3</span><span class="pln"> </span><span class="lit">4</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span><span class="pln">
</span><span class="roman"><span class="pun">…</span></span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="lit">0</span><span class="pln">  </span><span class="lit">0</span><span class="pln">  </span><span class="lit">0</span><span class="pln">  </span><span class="lit">0</span><span class="pln">   </span><span class="lit">-1</span><span class="pln">   </span><span class="lit">0</span><span class="pln">  </span><span class="lit">0</span><span class="pln">  </span><span class="lit">0</span><span class="pln">   </span><span class="lit">0</span><span class="pln">   </span><span class="lit">1</span><span class="pln">  </span><span class="lit">0</span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="roman"><span class="pun">…</span></span>
</pre></div>

<p>In Alyssa’s system, the signal from the sensor is represented as a stream
<code>sense-data</code> and the stream <code>zero-crossings</code> is the corresponding
stream of zero crossings.  Alyssa first writes a procedure
<code>sign-change-detector</code> that takes two values as arguments and compares the
signs of the values to produce an appropriate <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mn>0</mn>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mn>1</mn>
</math>, or <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo>−<!-- − --></mo>
    <mn>1</mn>
  </mrow>
</math>.  She then
constructs her zero-crossing stream as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-zero-crossings
         input-stream last-value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream
   </span><span class="opn">(</span><span class="pln">sign-change-detector 
    </span><span class="opn">(</span><span class="pln">stream-car input-stream</span><span class="clo">)</span><span class="pln"> 
    last-value</span><span class="clo">)</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">make-zero-crossings 
    </span><span class="opn">(</span><span class="pln">stream-cdr input-stream</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">stream-car input-stream</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> zero-crossings 
  </span><span class="opn">(</span><span class="pln">make-zero-crossings sense-data </span><span class="lit">0</span><span class="clo">))</span></pre></div>

<p>Alyssa’s boss, Eva Lu Ator, walks by and suggests that this program is
approximately equivalent to the following one, which uses the generalized
version of <code>stream-map</code> from <a href="#Exercise-3_002e50">Exercise 3.50</a>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> zero-crossings
  </span><span class="opn">(</span><span class="pln">stream-map sign-change-detector 
              sense-data 
              ⟨</span><var><span class="pln">expression</span></var><span class="pln">⟩</span><span class="clo">))</span></pre></div>

<p>Complete the program by supplying the indicated <code>⟨</code><var>expression</var><code>⟩</code>.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e75"></a>Exercise 3.75:</strong> Unfortunately, Alyssa’s
zero-crossing detector in <a href="#Exercise-3_002e74">Exercise 3.74</a> proves to be insufficient,
because the noisy signal from the sensor leads to spurious zero crossings.  Lem
E.  Tweakit, a hardware specialist, suggests that Alyssa smooth the signal to
filter out the noise before extracting the zero crossings.  Alyssa takes his
advice and decides to extract the zero crossings from the signal constructed by
averaging each value of the sense data with the previous value.  She explains
the problem to her assistant, Louis Reasoner, who attempts to implement the
idea, altering Alyssa’s program as follows:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-zero-crossings 
         input-stream last-value</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">avpt 
         </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-car input-stream</span><span class="clo">)</span><span class="pln"> 
               last-value</span><span class="clo">)</span><span class="pln"> 
            </span><span class="lit">2</span><span class="clo">)))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">cons-stream 
     </span><span class="opn">(</span><span class="pln">sign-change-detector avpt last-value</span><span class="clo">)</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">make-zero-crossings 
      </span><span class="opn">(</span><span class="pln">stream-cdr input-stream</span><span class="clo">)</span><span class="pln"> avpt</span><span class="clo">))))</span></pre></div>

<p>This does not correctly implement Alyssa’s plan.  Find the bug that Louis has
installed and fix it without changing the structure of the program.  (Hint: You
will need to increase the number of arguments to <code>make-zero-crossings</code>.)
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e76"></a>Exercise 3.76:</strong> Eva Lu Ator has a criticism of
Louis’s approach in <a href="#Exercise-3_002e75">Exercise 3.75</a>.  The program he wrote is not modular,
because it intermixes the operation of smoothing with the zero-crossing
extraction.  For example, the extractor should not have to be changed if Alyssa
finds a better way to condition her input signal.  Help Louis by writing a
procedure <code>smooth</code> that takes a stream as input and produces a stream in
which each element is the average of two successive input stream elements.
Then use <code>smooth</code> as a component to implement the zero-crossing detector
in a more modular style.
</p></blockquote>

<a id="g_t3_002e5_002e4"></a>
<a id="Streams-and-Delayed-Evaluation"></a>
<h4 class="subsection"><span class="secnum">3.5.4</span><span class="sectitle">Streams and Delayed Evaluation</span></h4>

<p>The <code>integral</code> procedure at the end of the preceding section shows how we
can use streams to model signal-processing systems that contain feedback loops.
The feedback loop for the adder shown in <a href="#Figure-3_002e32">Figure 3.32</a> is modeled by the
fact that <code>integral</code>’s internal stream <code>int</code> is defined in terms of
itself:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> int
  </span><span class="opn">(</span><span class="pln">cons-stream 
   initial-value
   </span><span class="opn">(</span><span class="pln">add-streams 
    </span><span class="opn">(</span><span class="pln">scale-stream integrand dt</span><span class="clo">)</span><span class="pln"> int</span><span class="clo">)))</span></pre></div>

<p>The interpreter’s ability to deal with such an implicit definition depends on
the <code>delay</code> that is incorporated into <code>cons-stream</code>.  Without this
<code>delay</code>, the interpreter could not construct <code>int</code> before evaluating
both arguments to <code>cons-stream</code>, which would require that <code>int</code>
already be defined.  In general, <code>delay</code> is crucial for using streams to
model signal-processing systems that contain loops.  Without <code>delay</code>, our
models would have to be formulated so that the inputs to any signal-processing
component would be fully evaluated before the output could be produced.  This
would outlaw loops.
</p>
<p>Unfortunately, stream models of systems with loops may require uses of
<code>delay</code> beyond the “hidden” <code>delay</code> supplied by <code>cons-stream</code>.
For instance, <a href="#Figure-3_002e34">Figure 3.34</a> shows a signal-processing system for solving
the differential equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <mi>t</mi>
    <mo>=</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> where <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> is a given
function.  The figure shows a mapping component, which applies <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> to its
input signal, linked in a feedback loop to an integrator in a manner very
similar to that of the analog computer circuits that are actually used to solve
such equations.
</p>
<figure class="float">
<a id="Figure-3_002e34"></a>
<object style="width: 44.98ex; height: 18.91ex;" data="fig/chap3/Fig3.34.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.34:</strong> An “analog computer circuit” that solves the equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <mi>t</mi>
    <mo>=</mo>
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.</p>
</figcaption>
</figure>

<p>Assuming we are given an initial value <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>y</mi>
    <mn>0</mn>
  </msub>
</math> for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>, we could try to model
this system using the procedure
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">solve f y0 dt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> y </span><span class="opn">(</span><span class="pln">integral dy y0 dt</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> dy </span><span class="opn">(</span><span class="pln">stream-map f y</span><span class="clo">))</span><span class="pln">
  y</span><span class="clo">)</span></pre></div>

<p>This procedure does not work, because in the first line of <code>solve</code> the
call to <code>integral</code> requires that the input <code>dy</code> be defined, which
does not happen until the second line of <code>solve</code>.
</p>
<p>On the other hand, the intent of our definition does make sense, because we
can, in principle, begin to generate the <code>y</code> stream without knowing
<code>dy</code>.  Indeed, <code>integral</code> and many other stream operations have
properties similar to those of <code>cons-stream</code>, in that we can generate part
of the answer given only partial information about the arguments.  For
<code>integral</code>, the first element of the output stream is the specified
<code>initial-value</code>.  Thus, we can generate the first element of the output
stream without evaluating the integrand <code>dy</code>.  Once we know the first
element of <code>y</code>, the <code>stream-map</code> in the second line of <code>solve</code>
can begin working to generate the first element of <code>dy</code>, which will
produce the next element of <code>y</code>, and so on.
</p>
<p>To take advantage of this idea, we will redefine <code>integral</code> to expect the
integrand stream to be a <a id="index-delayed-argument"></a>
<em>delayed argument</em>.  <code>Integral</code> will
<code>force</code> the integrand to be evaluated only when it is required to generate
more than the first element of the output stream:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">integral
         delayed-integrand initial-value dt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> int
    </span><span class="opn">(</span><span class="pln">cons-stream 
     initial-value
     </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">integrand 
            </span><span class="opn">(</span><span class="pln">force delayed-integrand</span><span class="clo">)))</span><span class="pln">
       </span><span class="opn">(</span><span class="pln">add-streams 
        </span><span class="opn">(</span><span class="pln">scale-stream integrand dt</span><span class="clo">)</span><span class="pln">
        int</span><span class="clo">))))</span><span class="pln">
  int</span><span class="clo">)</span></pre></div>

<p>Now we can implement our <code>solve</code> procedure by delaying the evaluation of
<code>dy</code> in the definition of <code>y</code>:<a class="footnote_link" id="DOCF199" href="#FOOT199"><sup>199</sup></a>
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">solve f y0 dt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> y </span><span class="opn">(</span><span class="pln">integral </span><span class="opn">(</span><span class="kwd">delay</span><span class="pln"> dy</span><span class="clo">)</span><span class="pln"> y0 dt</span><span class="clo">))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> dy </span><span class="opn">(</span><span class="pln">stream-map f y</span><span class="clo">))</span><span class="pln">
  y</span><span class="clo">)</span></pre></div>

<p>In general, every caller of <code>integral</code> must now <code>delay</code> the integrand
argument.  We can demonstrate that the <code>solve</code> procedure works by
approximating <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>e</mi>
    <mo>≈<!-- ≈ --></mo>
    <mn>2.718</mn>
  </mrow>
</math> by computing the value at <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math> of the
solution to the differential equation <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <mi>t</mi>
    <mo>=</mo>
    <mi>y</mi>
  </mrow>
</math> with initial
condition <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>y</mi>
    <mo stretchy="false">(</mo>
    <mn>0</mn>
    <mo stretchy="false">)</mo>
    <mo>=</mo>
    <mn>1</mn>
  </mrow>
</math>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="pln">stream-ref 
 </span><span class="opn">(</span><span class="pln">solve </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">y</span><span class="clo">)</span><span class="pln"> y</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="pln"> </span><span class="lit">0.001</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1000</span><span class="clo">)</span><span class="pln">
</span><i><span class="lit">2.716924</span></i>
</pre></div>

<blockquote>
<p><strong><a id="Exercise-3_002e77"></a>Exercise 3.77:</strong> The <code>integral</code> procedure
used above was analogous to the “implicit” definition of the infinite stream
of integers in <a href="#g_t3_002e5_002e2">3.5.2</a>.  Alternatively, we can give a definition of
<code>integral</code> that is more like <code>integers-starting-from</code> (also in
<a href="#g_t3_002e5_002e2">3.5.2</a>):
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">integral
         integrand initial-value dt</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream 
   initial-value
   </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-null? integrand</span><span class="clo">)</span><span class="pln">
       the-empty-stream
       </span><span class="opn">(</span><span class="pln">integral 
        </span><span class="opn">(</span><span class="pln">stream-cdr integrand</span><span class="clo">)</span><span class="pln">
        </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> </span><span class="opn">(</span><span class="pun">*</span><span class="pln"> dt </span><span class="opn">(</span><span class="pln">stream-car integrand</span><span class="clo">))</span><span class="pln">
           initial-value</span><span class="clo">)</span><span class="pln">
        dt</span><span class="clo">))))</span></pre></div>

<p>When used in systems with loops, this procedure has the same problem as does
our original version of <code>integral</code>.  Modify the procedure so that it
expects the <code>integrand</code> as a delayed argument and hence can be used in the
<code>solve</code> procedure shown above.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e78"></a>Exercise 3.78:</strong> Consider the problem of designing
a signal-processing system to study the homogeneous second-order linear
differential equation
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mfrac>
    <mrow>
      <msup>
        <mi>d</mi>
        <mn>2</mn>
      </msup>
      <mi>y</mi>
    </mrow>
    <mrow>
      <mi>d</mi>
      <msup>
        <mi>t</mi>
        <mn>2</mn>
      </msup>
    </mrow>
  </mfrac>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>a</mi>
    <mfrac>
      <mrow>
        <mi>d</mi>
        <mi>y</mi>
      </mrow>
      <mrow>
        <mi>d</mi>
        <mi>t</mi>
      </mrow>
    </mfrac>
  </mrow>
  <mo>−<!-- − --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>b</mi>
    <mi>y</mi>
  </mrow>
  <mspace width="thinmathspace"/>
  <mo>=</mo>
  <mspace width="thinmathspace"/>
  <mrow class="MJX-TeXAtom-ORD">
    <mn>0.</mn>
  </mrow>
</math>
The output stream, modeling <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>, is generated by a network that contains a
loop. This is because the value of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>d</mi>
      <mn>2</mn>
    </msup>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <msup>
      <mi>t</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math> depends upon the
values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math> and both of these are determined by
integrating <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>d</mi>
      <mn>2</mn>
    </msup>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <msup>
      <mi>t</mi>
      <mn>2</mn>
    </msup>
  </mrow>
</math>.  The diagram we would like to encode is
shown in <a href="#Figure-3_002e35">Figure 3.35</a>.  Write a procedure <code>solve-2nd</code> that takes as
arguments the constants <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>a</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>b</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math> and the initial values
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>y</mi>
    <mn>0</mn>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <msub>
      <mi>y</mi>
      <mn>0</mn>
    </msub>
  </mrow>
</math> for <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math> and generates the
stream of successive values of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>y</mi>
</math>.
</p></blockquote>

<figure class="float">
<a id="Figure-3_002e35"></a>
<object style="width: 44.72ex; height: 38.94ex;" data="fig/chap3/Fig3.35b.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.35:</strong> Signal-flow diagram for the solution to a second-order linear differential equation.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-3_002e79"></a>Exercise 3.79:</strong> Generalize the <code>solve-2nd</code>
procedure of <a href="#Exercise-3_002e78">Exercise 3.78</a> so that it can be used to solve general
second-order differential equations <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msup>
      <mi>d</mi>
      <mn>2</mn>
    </msup>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <msup>
      <mi>t</mi>
      <mn>2</mn>
    </msup>
  </mrow>
  <mo>=</mo>
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>d</mi>
    <mi>y</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mo>/</mo>
    </mrow>
    <mi>d</mi>
    <mi>t</mi>
    <mo>,</mo>
    <mi>y</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math>.
</p></blockquote>

<figure class="float">
<a id="Figure-3_002e36"></a>
<object style="width: 40.49ex; height: 21.76ex;" data="fig/chap3/Fig3.36.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.36:</strong> A series RLC circuit.</p>
</figcaption>
</figure>

<blockquote>
<p><strong><a id="Exercise-3_002e80"></a>Exercise 3.80:</strong> A <a id="index-series-RLC-circuit"></a>
<em>series RLC circuit</em>
consists of a resistor, a capacitor, and an inductor connected in series, as
shown in <a href="#Figure-3_002e36">Figure 3.36</a>.  If <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>R</mi>
</math>, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>L</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math> are the resistance,
inductance, and capacitance, then the relations between voltage <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>v</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> and
current <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> for the three components are described by the equations
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <msub>
          <mi>v</mi>
          <mi>R</mi>
        </msub>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <msub>
          <mi>i</mi>
          <mi>R</mi>
        </msub>
        <mi>R</mi>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msub>
          <mi>v</mi>
          <mi>L</mi>
        </msub>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mi>L</mi>
        <mspace width="thinmathspace"/>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <msub>
                <mi>i</mi>
                <mi>L</mi>
              </msub>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>t</mi>
            </mrow>
          </mfrac>
        </mrow>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msub>
          <mi>i</mi>
          <mi>C</mi>
        </msub>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mi>C</mi>
        <mspace width="thinmathspace"/>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <msub>
                <mi>v</mi>
                <mi>C</mi>
              </msub>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>t</mi>
            </mrow>
          </mfrac>
        </mrow>
        <mo>,</mo>
      </mtd>
    </mtr>
  </mtable>
</math>
and the circuit connections dictate the relations
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <msub>
          <mi>i</mi>
          <mi>R</mi>
        </msub>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <msub>
          <mi>i</mi>
          <mi>L</mi>
        </msub>
        <mo>=</mo>
        <mo>−<!-- − --></mo>
        <msub>
          <mi>i</mi>
          <mi>C</mi>
        </msub>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <msub>
          <mi>v</mi>
          <mi>C</mi>
        </msub>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <msub>
          <mi>v</mi>
          <mi>L</mi>
        </msub>
        <mo>+</mo>
        <msub>
          <mi>v</mi>
          <mi>R</mi>
        </msub>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>
Combining these equations shows that the state of the circuit (summarized by
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>v</mi>
    <mi>C</mi>
  </msub>
</math>, the voltage across the capacitor, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>i</mi>
    <mi>L</mi>
  </msub>
</math>, the current in
the inductor) is described by the pair of differential equations
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mtable columnalign="right center left" rowspacing="3pt" columnspacing="thickmathspace">
    <mtr>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <msub>
                <mi>v</mi>
                <mi>C</mi>
              </msub>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>t</mi>
            </mrow>
          </mfrac>
        </mrow>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mo>−<!-- − --></mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <msub>
              <mi>i</mi>
              <mi>L</mi>
            </msub>
            <mi>C</mi>
          </mfrac>
        </mrow>
        <mspace width="thinmathspace"/>
        <mo>,</mo>
      </mtd>
    </mtr>
    <mtr>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mrow>
              <mi>d</mi>
              <msub>
                <mi>i</mi>
                <mi>L</mi>
              </msub>
            </mrow>
            <mrow>
              <mi>d</mi>
              <mi>t</mi>
            </mrow>
          </mfrac>
        </mrow>
      </mtd>
      <mtd>
        <mo>=</mo>
      </mtd>
      <mtd>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mn>1</mn>
            <mi>L</mi>
          </mfrac>
        </mrow>
        <mspace width="thinmathspace"/>
        <msub>
          <mi>v</mi>
          <mi>C</mi>
        </msub>
        <mo>−<!-- − --></mo>
        <mrow class="MJX-TeXAtom-ORD">
          <mfrac>
            <mi>R</mi>
            <mi>L</mi>
          </mfrac>
        </mrow>
        <mspace width="thinmathspace"/>
        <msub>
          <mi>i</mi>
          <mi>L</mi>
        </msub>
        <mo>.</mo>
      </mtd>
    </mtr>
  </mtable>
</math>
The signal-flow diagram representing this system of differential equations is
shown in <a href="#Figure-3_002e37">Figure 3.37</a>.
</p></blockquote>

<figure class="float">
<a id="Figure-3_002e37"></a>
<object style="width: 42.48ex; height: 49.30ex;" data="fig/chap3/Fig3.37.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.37:</strong> A signal-flow diagram for the solution to a series RLC circuit.</p>
</figcaption>
</figure>

<blockquote>
<p>Write a procedure <code>RLC</code> that takes as arguments the parameters <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>R</mi>
</math>,
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>L</mi>
</math>, and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math> of the circuit and the time increment <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math>.  In a manner
similar to that of the <code>RC</code> procedure of <a href="#Exercise-3_002e73">Exercise 3.73</a>, <code>RLC</code>
should produce a procedure that takes the initial values of the state
variables, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>v</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <msub>
        <mi>C</mi>
        <mn>0</mn>
      </msub>
    </mrow>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>i</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <msub>
        <mi>L</mi>
        <mn>0</mn>
      </msub>
    </mrow>
  </msub>
</math>, and produces a pair (using
<code>cons</code>) of the streams of states <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>v</mi>
    <mi>C</mi>
  </msub>
</math> and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>i</mi>
    <mi>L</mi>
  </msub>
</math>.  Using
<code>RLC</code>, generate the pair of streams that models the behavior of a series
RLC circuit with <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>R</mi>
</math> = 1 ohm, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>C</mi>
</math> = 0.2 farad, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>L</mi>
</math> = 1 henry, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>d</mi>
    <mi>t</mi>
  </mrow>
</math>
= 0.1 second, and initial values <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>i</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <msub>
        <mi>L</mi>
        <mn>0</mn>
      </msub>
    </mrow>
  </msub>
</math> = 0 amps and <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>v</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <msub>
        <mi>C</mi>
        <mn>0</mn>
      </msub>
    </mrow>
  </msub>
</math> =
10 volts.
</p></blockquote>

<a id="Normal_002dorder-evaluation"></a>
<h5 class="subsubheading">Normal-order evaluation</h5>

<p>The examples in this section illustrate how the explicit use of <code>delay</code>
and <code>force</code> provides great programming flexibility, but the same examples
also show how this can make our programs more complex.  Our new <code>integral</code>
procedure, for instance, gives us the power to model systems with loops, but we
must now remember that <code>integral</code> should be called with a delayed
integrand, and every procedure that uses <code>integral</code> must be aware of this.
In effect, we have created two classes of procedures: ordinary procedures and
procedures that take delayed arguments.  In general, creating separate classes
of procedures forces us to create separate classes of higher-order procedures
as well.<a class="footnote_link" id="DOCF200" href="#FOOT200"><sup>200</sup></a>
</p>
<p>One way to avoid the need for two different classes of procedures is to make
all procedures take delayed arguments.  We could adopt a model of evaluation in
which all arguments to procedures are automatically delayed and arguments are
forced only when they are actually needed (for example, when they are required
by a primitive operation).  This would transform our language to use
normal-order evaluation, which we first described when we introduced the
substitution model for evaluation in <a href="1_002e1.xhtml#g_t1_002e1_002e5">1.1.5</a>.  Converting to
normal-order evaluation provides a uniform and elegant way to simplify the use
of delayed evaluation, and this would be a natural strategy to adopt if we were
concerned only with stream processing.  In <a href="4_002e2.xhtml#g_t4_002e2">4.2</a>, after we have
studied the evaluator, we will see how to transform our language in just this
way.  Unfortunately, including delays in procedure calls wreaks havoc with our
ability to design programs that depend on the order of events, such as programs
that use assignment, mutate data, or perform input or output.  Even the single
<code>delay</code> in <code>cons-stream</code> can cause great confusion, as illustrated by
<a href="#Exercise-3_002e51">Exercise 3.51</a> and <a href="#Exercise-3_002e52">Exercise 3.52</a>.  As far as anyone knows,
mutability and delayed evaluation do not mix well in programming languages, and
devising ways to deal with both of these at once is an active area of research.
</p>
<a id="g_t3_002e5_002e5"></a>
<a id="Modularity-of-Functional-Programs-and-Modularity-of-Objects"></a>
<h4 class="subsection"><span class="secnum">3.5.5</span><span class="sectitle">Modularity of Functional Programs and Modularity of Objects</span></h4>

<p>As we saw in <a href="3_002e1.xhtml#g_t3_002e1_002e2">3.1.2</a>, one of the major benefits of introducing
assignment is that we can increase the modularity of our systems by
encapsulating, or “hiding,” parts of the state of a large system within local
variables.  Stream models can provide an equivalent modularity without the use
of assignment.  As an illustration, we can reimplement the Monte Carlo
estimation of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>, which we examined in <a href="3_002e1.xhtml#g_t3_002e1_002e2">3.1.2</a>, from a
stream-processing point of view.
</p>
<p>The key modularity issue was that we wished to hide the internal state of a
random-number generator from programs that used random numbers.  We began with
a procedure <code>rand-update</code>, whose successive values furnished our supply of
random numbers, and used this to produce a random-number generator:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> rand
  </span><span class="opn">(</span><span class="kwd">let</span><span class="pln"> </span><span class="opn">((</span><span class="pln">x random-init</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> x </span><span class="opn">(</span><span class="pln">rand-update x</span><span class="clo">))</span><span class="pln">
      x</span><span class="clo">)))</span></pre></div>

<p>In the stream formulation there is no random-number generator <em>per se</em>,
just a stream of random numbers produced by successive calls to
<code>rand-update</code>:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> random-numbers
  </span><span class="opn">(</span><span class="pln">cons-stream random-init
               </span><span class="opn">(</span><span class="pln">stream-map rand-update 
                           random-numbers</span><span class="clo">)))</span></pre></div>

<p>We use this to construct the stream of outcomes of the Cesàro experiment
performed on consecutive pairs in the <code>random-numbers</code> stream:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> cesaro-stream
  </span><span class="opn">(</span><span class="pln">map-successive-pairs
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">r1 r2</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pun">=</span><span class="pln"> </span><span class="opn">(</span><span class="pln">gcd r1 r2</span><span class="clo">)</span><span class="pln"> </span><span class="lit">1</span><span class="clo">))</span><span class="pln">
   random-numbers</span><span class="clo">))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">map-successive-pairs f s</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream
   </span><span class="opn">(</span><span class="pln">f </span><span class="opn">(</span><span class="pln">stream-car s</span><span class="clo">)</span><span class="pln"> 
      </span><span class="opn">(</span><span class="pln">stream-car </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">map-successive-pairs 
    f </span><span class="opn">(</span><span class="pln">stream-cdr </span><span class="opn">(</span><span class="pln">stream-cdr s</span><span class="clo">)))))</span></pre></div>

<p>The <code>cesaro-stream</code> is now fed to a <code>monte-carlo</code> procedure, which
produces a stream of estimates of probabilities.  The results are then
converted into a stream of estimates of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math>.  This version of the program
doesn’t need a parameter telling how many trials to perform.  Better estimates
of <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>π<!-- π --></mi>
</math> (from performing more experiments) are obtained by looking farther
into the <code>pi</code> stream:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">monte-carlo experiment-stream 
                     passed 
                     failed</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">next passed failed</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">cons-stream
     </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> passed </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> passed failed</span><span class="clo">))</span><span class="pln">
     </span><span class="opn">(</span><span class="pln">monte-carlo
      </span><span class="opn">(</span><span class="pln">stream-cdr experiment-stream</span><span class="clo">)</span><span class="pln"> 
      passed 
      failed</span><span class="clo">)))</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">if</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-car experiment-stream</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">next </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> passed </span><span class="lit">1</span><span class="clo">)</span><span class="pln"> failed</span><span class="clo">)</span><span class="pln">
      </span><span class="opn">(</span><span class="pln">next passed </span><span class="opn">(</span><span class="pun">+</span><span class="pln"> failed </span><span class="lit">1</span><span class="clo">))))</span><span class="pln">

</span><span class="opn">(</span><span class="kwd">define</span><span class="pln"> pi
  </span><span class="opn">(</span><span class="pln">stream-map
   </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">p</span><span class="clo">)</span><span class="pln"> </span><span class="opn">(</span><span class="pln">sqrt </span><span class="opn">(</span><span class="pun">/</span><span class="pln"> </span><span class="lit">6</span><span class="pln"> p</span><span class="clo">)))</span><span class="pln">
   </span><span class="opn">(</span><span class="pln">monte-carlo cesaro-stream </span><span class="lit">0</span><span class="pln"> </span><span class="lit">0</span><span class="clo">)))</span></pre></div>

<p>There is considerable modularity in this approach, because we still can
formulate a general <code>monte-carlo</code> procedure that can deal with arbitrary
experiments.  Yet there is no assignment or local state.
</p>
<blockquote>
<p><strong><a id="Exercise-3_002e81"></a>Exercise 3.81:</strong> <a href="3_002e1.xhtml#Exercise-3_002e6">Exercise 3.6</a> discussed
generalizing the random-number generator to allow one to reset the
random-number sequence so as to produce repeatable sequences of “random”
numbers.  Produce a stream formulation of this same generator that operates on
an input stream of requests to <code>generate</code> a new random number or to
<code>reset</code> the sequence to a specified value and that produces the desired
stream of random numbers.  Don’t use assignment in your solution.
</p></blockquote>

<blockquote>
<p><strong><a id="Exercise-3_002e82"></a>Exercise 3.82:</strong> Redo <a href="3_002e1.xhtml#Exercise-3_002e5">Exercise 3.5</a> on Monte
Carlo integration in terms of streams.  The stream version of
<code>estimate-integral</code> will not have an argument telling how many trials to
perform.  Instead, it will produce a stream of estimates based on successively
more trials.
</p></blockquote>

<a id="A-functional_002dprogramming-view-of-time"></a>
<h5 class="subsubheading">A functional-programming view of time</h5>

<p>Let us now return to the issues of objects and state that were raised at the
beginning of this chapter and examine them in a new light.  We introduced
assignment and mutable objects to provide a mechanism for modular construction
of programs that model systems with state.  We constructed computational
objects with local state variables and used assignment to modify these
variables.  We modeled the temporal behavior of the objects in the world by the
temporal behavior of the corresponding computational objects.
</p>
<p>Now we have seen that streams provide an alternative way to model objects with
local state.  We can model a changing quantity, such as the local state of some
object, using a stream that represents the time history of successive states.
In essence, we represent time explicitly, using streams, so that we decouple
time in our simulated world from the sequence of events that take place during
evaluation.  Indeed, because of the presence of <code>delay</code> there may be
little relation between simulated time in the model and the order of events
during the evaluation.
</p>
<p>In order to contrast these two approaches to modeling, let us reconsider the
implementation of a “withdrawal processor” that monitors the balance in a
bank account.  In <a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a> we implemented a simplified version of
such a processor:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">make-simplified-withdraw balance</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="kwd">lambda</span><span class="pln"> </span><span class="opn">(</span><span class="pln">amount</span><span class="clo">)</span><span class="pln">
    </span><span class="opn">(</span><span class="kwd">set</span><span class="pun">!</span><span class="pln"> balance </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance amount</span><span class="clo">))</span><span class="pln">
    balance</span><span class="clo">))</span></pre></div>

<p>Calls to <code>make-simplified-withdraw</code> produce computational objects, each
with a local state variable <code>balance</code> that is decremented by successive
calls to the object.  The object takes an <code>amount</code> as an argument and
returns the new balance.  We can imagine the user of a bank account typing a
sequence of inputs to such an object and observing the sequence of returned
values shown on a display screen.
</p>
<p>Alternatively, we can model a withdrawal processor as a procedure that takes as
input a balance and a stream of amounts to withdraw and produces the stream of
successive balances in the account:
</p>
<div class="lisp">
<pre class="lisp prettyprinted" style=""><span class="opn">(</span><span class="kwd">define</span><span class="pln"> </span><span class="opn">(</span><span class="pln">stream-withdraw balance amount-stream</span><span class="clo">)</span><span class="pln">
  </span><span class="opn">(</span><span class="pln">cons-stream
   balance
   </span><span class="opn">(</span><span class="pln">stream-withdraw 
    </span><span class="opn">(</span><span class="pun">-</span><span class="pln"> balance </span><span class="opn">(</span><span class="pln">stream-car amount-stream</span><span class="clo">))</span><span class="pln">
    </span><span class="opn">(</span><span class="pln">stream-cdr amount-stream</span><span class="clo">))))</span></pre></div>

<p><code>Stream-withdraw</code> implements a well-defined mathematical function whose
output is fully determined by its input.  Suppose, however, that the input
<code>amount-stream</code> is the stream of successive values typed by the user and
that the resulting stream of balances is displayed.  Then, from the perspective
of the user who is typing values and watching results, the stream process has
the same behavior as the object created by <code>make-simplified-withdraw</code>.
However, with the stream version, there is no assignment, no local state
variable, and consequently none of the theoretical difficulties that we
encountered in <a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a>.  Yet the system has state!
</p>
<p>This is really remarkable.  Even though <code>stream-withdraw</code> implements a
well-defined mathematical function whose behavior does not change, the user’s
perception here is one of interacting with a system that has a changing state.
One way to resolve this paradox is to realize that it is the user’s temporal
existence that imposes state on the system.  If the user could step back from
the interaction and think in terms of streams of balances rather than
individual transactions, the system would appear stateless.<a class="footnote_link" id="DOCF201" href="#FOOT201"><sup>201</sup></a>
</p>
<p>From the point of view of one part of a complex process, the other parts appear
to change with time.  They have hidden time-varying local state.  If we wish to
write programs that model this kind of natural decomposition in our world (as
we see it from our viewpoint as a part of that world) with structures in our
computer, we make computational objects that are not functional—they must
change with time.  We model state with local state variables, and we model the
changes of state with assignments to those variables.  By doing this we make
the time of execution of a computation model time in the world that we are part
of, and thus we get “objects” in our computer.
</p>
<p>Modeling with objects is powerful and intuitive, largely because this matches
the perception of interacting with a world of which we are part.  However, as
we’ve seen repeatedly throughout this chapter, these models raise thorny
problems of constraining the order of events and of synchronizing multiple
processes.  The possibility of avoiding these problems has stimulated the
development of <a id="index-functional-programming-languages"></a>
<em>functional programming languages</em>, which do not include
any provision for assignment or mutable data.  In such a language, all
procedures implement well-defined mathematical functions of their arguments,
whose behavior does not change.  The functional approach is extremely
attractive for dealing with concurrent systems.<a class="footnote_link" id="DOCF202" href="#FOOT202"><sup>202</sup></a>
</p>
<p>On the other hand, if we look closely, we can see time-related problems
creeping into functional models as well.  One particularly troublesome area
arises when we wish to design interactive systems, especially ones that model
interactions between independent entities.  For instance, consider once more
the implementation of a banking system that permits joint bank accounts.  In a
conventional system using assignment and objects, we would model the fact that
Peter and Paul share an account by having both Peter and Paul send their
transaction requests to the same bank-account object, as we saw in 
<a href="3_002e1.xhtml#g_t3_002e1_002e3">3.1.3</a>.  From the stream point of view, where there are no “objects”
<em>per se</em>, we have already indicated that a bank account can be modeled as
a process that operates on a stream of transaction requests to produce a stream
of responses.  Accordingly, we could model the fact that Peter and Paul have a
joint bank account by merging Peter’s stream of transaction requests with
Paul’s stream of requests and feeding the result to the bank-account stream
process, as shown in <a href="#Figure-3_002e38">Figure 3.38</a>.
</p>
<figure class="float">
<a id="Figure-3_002e38"></a>
<object style="width: 54.65ex; height: 9.76ex;" data="fig/chap3/Fig3.38a.std.svg" type="image/svg+xml">SVG</object>

<figcaption class="float-caption">
<p><strong>Figure 3.38:</strong> A joint bank account, modeled by merging two streams of transaction requests.</p>
</figcaption>
</figure>

<p>The trouble with this formulation is in the notion of <a id="index-merge"></a>
<em>merge</em>.  It will
not do to merge the two streams by simply taking alternately one request from
Peter and one request from Paul. Suppose Paul accesses the account only very
rarely.  We could hardly force Peter to wait for Paul to access the account
before he could issue a second transaction.  However such a merge is
implemented, it must interleave the two transaction streams in some way that is
constrained by “real time” as perceived by Peter and Paul, in the sense that,
if Peter and Paul meet, they can agree that certain transactions were processed
before the meeting, and other transactions were processed after the
meeting.<a class="footnote_link" id="DOCF203" href="#FOOT203"><sup>203</sup></a> This
is precisely the same constraint that we had to deal with in 
<a href="3_002e4.xhtml#g_t3_002e4_002e1">3.4.1</a>, where we found the need to introduce explicit synchronization to
ensure a “correct” order of events in concurrent processing of objects with
state.  Thus, in an attempt to support the functional style, the need to merge
inputs from different agents reintroduces the same problems that the functional
style was meant to eliminate.
</p>
<p>We began this chapter with the goal of building computational models whose
structure matches our perception of the real world we are trying to model.  We
can model the world as a collection of separate, time-bound, interacting
objects with state, or we can model the world as a single, timeless, stateless
unity.  Each view has powerful advantages, but neither view alone is completely
satisfactory.  A grand unification has yet to emerge.<a class="footnote_link" id="DOCF204" href="#FOOT204"><sup>204</sup></a>
</p>
<div class="footnote">
<h4 class="footnotes-heading">Footnotes</h4>

<div id="FOOT180"><p><a class="footnote_backlink" href="#DOCF180"><sup>180</sup></a>
Physicists sometimes
adopt this view by introducing the “world lines” of particles as a device for
reasoning about motion.  We’ve also already mentioned (<a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>)
that this is the natural way to think about signal-processing systems.  We will
explore applications of streams to signal processing in <a href="#g_t3_002e5_002e3">3.5.3</a>.</p>
</div>
<div id="FOOT181"><p><a class="footnote_backlink" href="#DOCF181"><sup>181</sup></a>
Assume that we have a predicate <code>prime?</code> (e.g.,
as in <a href="1_002e2.xhtml#g_t1_002e2_002e6">1.2.6</a>) that tests for primality.</p>
</div>
<div id="FOOT182"><p><a class="footnote_backlink" href="#DOCF182"><sup>182</sup></a>
In the <abbr>MIT</abbr>
implementation, <code>the-empty-stream</code> is the same as the empty list
<code>'()</code>, and <code>stream-null?</code> is the same as <code>null?</code>.</p>
</div>
<div id="FOOT183"><p><a class="footnote_backlink" href="#DOCF183"><sup>183</sup></a>
This should bother
you.  The fact that we are defining such similar procedures for streams and
lists indicates that we are missing some underlying abstraction.
Unfortunately, in order to exploit this abstraction, we will need to exert
finer control over the process of evaluation than we can at present.  We will
discuss this point further at the end of <a href="#g_t3_002e5_002e4">3.5.4</a>.  In 
<a href="4_002e2.xhtml#g_t4_002e2">4.2</a>, we’ll develop a framework that unifies lists and streams.</p>
</div>
<div id="FOOT184"><p><a class="footnote_backlink" href="#DOCF184"><sup>184</sup></a>
Although <code>stream-car</code> and
<code>stream-cdr</code> can be defined as procedures, <code>cons-stream</code> must be a
special form.  If <code>cons-stream</code> were a procedure, then, according to our
model of evaluation, evaluating <code>(cons-stream ⟨<var>a</var>⟩ ⟨<var>b</var>⟩)</code> would
automatically cause <code>⟨</code><var>b</var><code>⟩</code> to be evaluated, which is precisely what we do
not want to happen.  For the same reason, <code>delay</code> must be a special form,
though <code>force</code> can be an ordinary procedure.</p>
</div>
<div id="FOOT185"><p><a class="footnote_backlink" href="#DOCF185"><sup>185</sup></a>
The numbers shown here do not really appear in
the delayed expression.  What actually appears is the original expression, in
an environment in which the variables are bound to the appropriate numbers.
For example, <code>(+ low 1)</code> with <code>low</code> bound to 10,000 actually appears
where <code>10001</code> is shown.</p>
</div>
<div id="FOOT186"><p><a class="footnote_backlink" href="#DOCF186"><sup>186</sup></a>
There are many possible
implementations of streams other than the one described in this section.
Delayed evaluation, which is the key to making streams practical, was inherent
in Algol 60’s <a id="index-call_002dby_002dname"></a>
<em>call-by-name</em> parameter-passing method.  The use of this
mechanism to implement streams was first described by <a href="References.xhtml#Landin-_00281965_0029">Landin (1965)</a>.  Delayed
evaluation for streams was introduced into Lisp by <a href="References.xhtml#Friedman-and-Wise-_00281976_0029">Friedman and Wise (1976)</a>. In
their implementation, <code>cons</code> always delays evaluating its arguments, so
that lists automatically behave as streams.  The memoizing optimization is also
known as <a id="index-call_002dby_002dneed"></a>
<em>call-by-need</em>.  The Algol community would refer to our
original delayed objects as <a id="index-call_002dby_002dname-thunks"></a>
<em>call-by-name thunks</em> and to the optimized
versions as <a id="index-call_002dby_002dneed-thunks"></a>
<em>call-by-need thunks</em>.</p>
</div>
<div id="FOOT187"><p><a class="footnote_backlink" href="#DOCF187"><sup>187</sup></a>
Exercises such as <a href="#Exercise-3_002e51">Exercise 3.51</a> and
<a href="#Exercise-3_002e52">Exercise 3.52</a> are valuable for testing our understanding of how
<code>delay</code> works.  On the other hand, intermixing delayed evaluation with
printing—and, even worse, with assignment—is extremely confusing, and
instructors of courses on computer languages have traditionally tormented their
students with examination questions such as the ones in this section.  Needless
to say, writing programs that depend on such subtleties is odious programming
style.  Part of the power of stream processing is that it lets us ignore the
order in which events actually happen in our programs.  Unfortunately, this is
precisely what we cannot afford to do in the presence of assignment, which
forces us to be concerned with time and change.</p>
</div>
<div id="FOOT188"><p><a class="footnote_backlink" href="#DOCF188"><sup>188</sup></a>
Eratosthenes, a third-century <abbr>B.C.</abbr>
Alexandrian Greek philosopher, is famous for giving the first accurate estimate
of the circumference of the Earth, which he computed by observing shadows cast
at noon on the day of the summer solstice.  Eratosthenes’s sieve method,
although ancient, has formed the basis for special-purpose hardware “sieves”
that, until recently, were the most powerful tools in existence for locating
large primes.  Since the 70s, however, these methods have been superseded by
outgrowths of the probabilistic techniques discussed in <a href="1_002e2.xhtml#g_t1_002e2_002e6">1.2.6</a>.</p>
</div>
<div id="FOOT189"><p><a class="footnote_backlink" href="#DOCF189"><sup>189</sup></a>
We have named these figures after Peter Henderson, who was the
first person to show us diagrams of this sort as a way of thinking about stream
processing.  Each solid line represents a stream of values being transmitted.
The dashed line from the <code>car</code> to the <code>cons</code> and the <code>filter</code>
indicates that this is a single value rather than a stream.</p>
</div>
<div id="FOOT190"><p><a class="footnote_backlink" href="#DOCF190"><sup>190</sup></a>
This uses the generalized version of <code>stream-map</code> from
<a href="#Exercise-3_002e50">Exercise 3.50</a>.</p>
</div>
<div id="FOOT191"><p><a class="footnote_backlink" href="#DOCF191"><sup>191</sup></a>
This last point is very subtle and relies on
the fact that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>p</mi>
      <mrow class="MJX-TeXAtom-ORD">
        <mi>n</mi>
        <mo>+</mo>
        <mn>1</mn>
      </mrow>
    </msub>
    <mo>≤<!-- ≤ --></mo>
    <msubsup>
      <mi>p</mi>
      <mi>n</mi>
      <mn>2</mn>
    </msubsup>
  </mrow>
  <mo>.</mo>
</math>  (Here, <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>p</mi>
    <mi>k</mi>
  </msub>
</math> denotes the
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msup>
    <mi>k</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mtext>th</mtext>
    </mrow>
  </msup>
</math> prime.)  Estimates such as these are very difficult to establish.  The
ancient proof by Euclid that there are an infinite number of primes shows that
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>p</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>n</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>≤<!-- ≤ --></mo>
  <mrow class="MJX-TeXAtom-ORD">
    <msub>
      <mi>p</mi>
      <mn>1</mn>
    </msub>
    <msub>
      <mi>p</mi>
      <mn>2</mn>
    </msub>
    <mo>⋯<!-- ⋯ --></mo>
    <msub>
      <mi>p</mi>
      <mi>n</mi>
    </msub>
    <mo>+</mo>
    <mn>1</mn>
  </mrow>
</math>, and no substantially
better result was proved until 1851, when the Russian mathematician
P. L. Chebyshev established that <math xmlns="http://www.w3.org/1998/Math/MathML">
  <msub>
    <mi>p</mi>
    <mrow class="MJX-TeXAtom-ORD">
      <mi>n</mi>
      <mo>+</mo>
      <mn>1</mn>
    </mrow>
  </msub>
  <mo>≤<!-- ≤ --></mo>
  <mn>2</mn>
  <msub>
    <mi>p</mi>
    <mi>n</mi>
  </msub>
</math> for all <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>n</mi>
</math>.
This result, originally conjectured in 1845, is known as <a id="index-Bertrand_0027s-hypothesis"></a>
<em>Bertrand’s hypothesis</em>.  
A proof can be found in section 22.3 of <a href="References.xhtml#Hardy-and-Wright-1960">Hardy and Wright 1960</a>.</p>
</div>
<div id="FOOT192"><p><a class="footnote_backlink" href="#DOCF192"><sup>192</sup></a>
This exercise shows how call-by-need is closely related
to ordinary memoization as described in <a href="3_002e3.xhtml#Exercise-3_002e27">Exercise 3.27</a>.  In that exercise,
we used assignment to explicitly construct a local table.  Our call-by-need
stream optimization effectively constructs such a table automatically, storing
values in the previously forced parts of the stream.</p>
</div>
<div id="FOOT193"><p><a class="footnote_backlink" href="#DOCF193"><sup>193</sup></a>
We can’t use <code>let</code>
to bind the local variable <code>guesses</code>, because the value of <code>guesses</code>
depends on <code>guesses</code> itself.  <a href="#Exercise-3_002e63">Exercise 3.63</a> addresses why we want a
local variable here.</p>
</div>
<div id="FOOT194"><p><a class="footnote_backlink" href="#DOCF194"><sup>194</sup></a>
As in 
<a href="2_002e2.xhtml#g_t2_002e2_002e3">2.2.3</a>, we represent a pair of integers as a list rather than a Lisp
pair.</p>
</div>
<div id="FOOT195"><p><a class="footnote_backlink" href="#DOCF195"><sup>195</sup></a>
See <a href="#Exercise-3_002e68">Exercise 3.68</a> for
some insight into why we chose this decomposition.</p>
</div>
<div id="FOOT196"><p><a class="footnote_backlink" href="#DOCF196"><sup>196</sup></a>
The precise statement of the required
property on the order of combination is as follows: There should be a function
<math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>f</mi>
</math> of two arguments such that the pair corresponding to element <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>i</mi>
</math> of the
first stream and element <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mi>j</mi>
</math> of the second stream will appear as element
number <math xmlns="http://www.w3.org/1998/Math/MathML">
  <mrow class="MJX-TeXAtom-ORD">
    <mi>f</mi>
    <mo stretchy="false">(</mo>
    <mi>i</mi>
    <mo>,</mo>
    <mi>j</mi>
    <mo stretchy="false">)</mo>
  </mrow>
</math> of the output stream.  The trick of using
<code>interleave</code> to accomplish this was shown to us by David Turner, who
employed it in the language KRC (<a href="References.xhtml#Turner-1981">Turner 1981</a>).</p>
</div>
<div id="FOOT197"><p><a class="footnote_backlink" href="#DOCF197"><sup>197</sup></a>
We will require that the weighting function be such that the
weight of a pair increases as we move out along a row or down along a column of
the array of pairs.</p>
</div>
<div id="FOOT198"><p><a class="footnote_backlink" href="#DOCF198"><sup>198</sup></a>
To quote from G. H. Hardy’s obituary of Ramanujan (<a href="References.xhtml#Hardy-1921">Hardy 1921</a>): 
“It was Mr. Littlewood (I believe) who remarked that ‘every positive
integer was one of his friends.’  I remember once going to see him when he was
lying ill at Putney.  I had ridden in taxi-cab No. 1729, and remarked that the
number seemed to me a rather dull one, and that I hoped it was not an
unfavorable omen.  ‘No,’ he replied, ‘it is a very interesting number; it is
the smallest number expressible as the sum of two cubes in two different ways.’
” The trick of using weighted pairs to generate the Ramanujan numbers was
shown to us by Charles Leiserson.</p>
</div>
<div id="FOOT199"><p><a class="footnote_backlink" href="#DOCF199"><sup>199</sup></a>
This procedure is not
guaranteed to work in all Scheme implementations, although for any
implementation there is a simple variation that will work.  The problem has to
do with subtle differences in the ways that Scheme implementations handle
internal definitions.  (See <a href="4_002e1.xhtml#g_t4_002e1_002e6">4.1.6</a>.)</p>
</div>
<div id="FOOT200"><p><a class="footnote_backlink" href="#DOCF200"><sup>200</sup></a>
This is a small reflection, in Lisp, of the difficulties that
conventional strongly typed languages such as Pascal have in coping with
higher-order procedures.  In such languages, the programmer must specify the
data types of the arguments and the result of each procedure: number, logical
value, sequence, and so on.  Consequently, we could not express an abstraction
such as “map a given procedure <code>proc</code> over all the elements in a
sequence” by a single higher-order procedure such as <code>stream-map</code>.
Rather, we would need a different mapping procedure for each different
combination of argument and result data types that might be specified for a
<code>proc</code>.  Maintaining a practical notion of “data type” in the presence
of higher-order procedures raises many difficult issues.  One way of dealing
with this problem is illustrated by the language ML (<a href="References.xhtml#Gordon-et-al_002e-1979">Gordon et al. 1979</a>), 
whose “polymorphic data types” include templates for
higher-order transformations between data types.  Moreover, data types for most
procedures in ML are never explicitly declared by the programmer.  Instead, ML
includes a <a id="index-type_002dinferencing"></a>
<em>type-inferencing</em> mechanism that uses information in the
environment to deduce the data types for newly defined procedures.</p>
</div>
<div id="FOOT201"><p><a class="footnote_backlink" href="#DOCF201"><sup>201</sup></a>
Similarly
in physics, when we observe a moving particle, we say that the position (state)
of the particle is changing.  However, from the perspective of the particle’s
world line in space-time there is no change involved.</p>
</div>
<div id="FOOT202"><p><a class="footnote_backlink" href="#DOCF202"><sup>202</sup></a>
John Backus, the
inventor of Fortran, gave high visibility to functional programming when he was
awarded the <abbr>ACM</abbr> Turing award in 1978.  His acceptance speech 
(<a href="References.xhtml#Backus-1978">Backus 1978</a>) strongly advocated the functional approach.  A good overview of
functional programming is given in <a href="References.xhtml#Henderson-1980">Henderson 1980</a> and in 
<a href="References.xhtml#Darlington-et-al_002e-1982">Darlington et al. 1982</a>.</p>
</div>
<div id="FOOT203"><p><a class="footnote_backlink" href="#DOCF203"><sup>203</sup></a>
Observe that, for any two streams, there is in general more
than one acceptable order of interleaving.  Thus, technically, “merge” is a
relation rather than a function—the answer is not a deterministic function of
the inputs.  We already mentioned (<a href="3_002e4.xhtml#Footnote-167">Footnote 167</a>) that nondeterminism is
essential when dealing with concurrency.  The merge relation illustrates the
same essential nondeterminism, from the functional perspective.  In 
<a href="4_002e3.xhtml#g_t4_002e3">4.3</a>, we will look at nondeterminism from yet another point of view.</p>
</div>
<div id="FOOT204"><p><a class="footnote_backlink" href="#DOCF204"><sup>204</sup></a>
The object model
approximates the world by dividing it into separate pieces.  The functional
model does not modularize along object boundaries.  The object model is useful
when the unshared state of the “objects” is much larger than the state that
they share.  An example of a place where the object viewpoint fails is quantum
mechanics, where thinking of things as individual particles leads to paradoxes
and confusions.  Unifying the object view with the functional view may have
little to do with programming, but rather with fundamental epistemological
issues.</p>
</div>
</div>
<nav class="header">
<p>
Next: <a href="Chapter-4.xhtml#Chapter-4" accesskey="n" rel="next">Chapter 4</a>, Prev: <a href="3_002e4.xhtml#g_t3_002e4" accesskey="p" rel="prev">3.4</a>, Up: <a href="#g_t3_002e5" accesskey="u" rel="prev">3.5</a>   [<a href="index.xhtml#SEC_Contents" title="Table of contents" accesskey="c" rel="contents">Contents</a>]</p>
</nav>


</section><span class="bottom jump" title="Jump to bottom"><a href="#pagebottom" accesskey="b">⇣</a></span><a id="pagebottom"></a>
</body>
</html>